Reverse Linked List Algorithm

Question

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;
}

Do you mean "I want to reverse it to 6 5 7"?

Will Da Silva
– Will Da Silva

2017-06-22 13:42:46 +00:00
Commented Jun 22, 2017 at 13:42 — Will Da Silva
– Will Da Silva, Commented Jun 22, 2017 at 13:42

Chinmay Relkar · Accepted Answer · 2017-06-22 13:53:14Z

1

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

answered Jun 22, 2017 at 13:53

Chinmay Relkar

4734 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

javidcf · Accepted Answer · 2017-06-22 14:10:00Z

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;
}

Collectives™ on Stack Overflow

Reverse Linked List Algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related