CODEWITHSUNDEEP
c++algorithmlinked-list
ThatOneCoderDude
ThatOneCoderDude

Reputation: 45

Reverse Linked List Algorithm

I made a algorithm that should reverse my linked list. Original List looks like 7 5 6 I want to reverse it to 5 6 7 . But when printing out the linked list after the reverse function I only see 5

NodeType * temp = start;
int dataHolder[length] = {0};
int runTime = length - 1;

for(int i = 0; i<length; i++){
    if(temp->next == NULL){
        break;
    }

    dataHolder[runTime] = temp->data;
    temp = temp->next;
    runTime--;
}

for(int j = 0; j<length; j++){
    if(start->next == NULL){
        break;
    }

    start->data = dataHolder[j];
    start = start->next;
}

Upvotes: 1

Views: 249

Answers (2)

javidcf
javidcf

Reputation: 59701

Both loops are missing one element, you should iterate until the current node is NULL, not until the next node is. In fact, you can just put that condition in a while loop instead of using a for loop, which may be more logical for a linked list (even if you already have precomputed the length). Also I suspect you are using the same start variable to check the result, which does not work because you are overwriting it. Try something like this:

NodeType * temp = start;
int dataHolder[length] = {0};
int runTime = length - 1;

while (temp != NULL) {
    dataHolder[runTime] = temp->data;
    temp = temp->next;
    runTime--;
}

temp = start;
runtime = 0;
while (temp != NULL) {
    temp->data = dataHolder[runtime];
    temp = temp->next;
    runtime++;
}

Addendum:

You can actually reverse a linked list in O(n) without using any additional memory (and without needing to precompute its length), just by reordering the pointers. There are some cases where this may not be acceptable (e.g. if you have external pointers or references to nodes that expect to see their value changed when you reverse the list), but most times it's fine. It would go something like this:

NodeType * temp1 = start;  // Assuming start is not NULL
NodeType * temp2 = start->next;
start->next = NULL;

while (temp2 != NULL) {
    NodeType * temp3 = temp2->next;
    temp2->next = temp1;
    temp1 = temp2;
    temp2 = temp3;
}

Upvotes: 0

Chinmay Relkar
Chinmay Relkar

Reputation: 473

Your algorithm is not working because in the first loop data in first n-1 nodes is copied in to the array dataHolder and then in the second loop you copy the array into the linked list in the same order as you retrieved it.

plus you are editing your "start" variable which is the only reference to the start of the list

at the end of the 2nd loop start points to the second last node in the list

and you display the linked list using the same "start" variable

for your entered data
7->5->6
after processing 1st loop in the dataholder
7 5
copying it into the linked list. Linked List is now
7->5
but start is pointing to 5

displaying the linked list using start so obviously 5 will only be printed

Upvotes: 1

Related Questions