Reversing linked list?

Suppose I have a linked list: 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL Your code converts it to: v | v | ---------- ---------- ---------- ---------- | 1 | |--->| 2 | | | 3 | | | 4 Notice that the first element still points back to 2 If you add the line parent->next = NULL after the first two, you will get: v | v | ---------- ---------- ---------- ---------- NULLnext; if(current == NULL) return parent; else { current = reverse_list_recursive(current); parent->next = NULL; current->next = parent; printf("\n %d \n",current->value); return parent; } }.

Suppose I have a linked list: ---------- ---------- ---------- ---------- | 1 | |--->| 2 | |--->| 3 | |--->| 4 | |--->NULL ---------- ---------- ---------- ---------- Your code converts it to: ---------------------- ---------------------- | | | | v | v | ---------- ---------- ---------- ---------- | 1 | |--->| 2 | | | 3 | | | 4 | | ---------- ---------- ---------- ---------- ^ | | | ---------------------- Notice that the first element still points back to 2. If you add the line parent->next = NULL after the first two, you will get: ---------------------- ---------------------- | | | | v | v | ---------- ---------- ---------- ---------- NULLnext; if(current == NULL) return parent; else { current = reverse_list_recursive(current); parent->next = NULL; current->next = parent; printf("\n %d \n",current->value); return parent; } }.

When you reach the end of the list, you return the last node. That last node's next value then gets assigned to itself, hence you'd create an inconsistency. If current is NULL, return NULL instead and simply disregard the rest of the code if the return is NULL.

Does not work when I did that in the above code... :( – ravi Nov 2 '10 at 15:00.

You forgot to update the next member of the first item on the linked list. Add parent->next = NULL; before the recursion call.

That does not work ... – ravi Nov 2 '10 at 15:07.

You need to set the new tail (i. E the old head)'s next pointer to NULL EDIT: Here's a recursive version node *reverse_list_recursive(node *list) { node *parent = list; node *child = list->next; node *new_head; if (child == NULL) return parent ; /* new head */ new_head = reverse_list_recursive(child) child->next = parent; /* Old parent is the new child of the old child when reversed */ parent->next = NULL; /* might be tail, will be overwritten after we return if we're not at the top level */ return new_head; }.

After the line current = reverse_list_recursive(current); you are storing the new list head in current, so current->next = parent; is wrong. New current is the new list head, but you need to access the new list tail, i.e. , the OLD current: node* newhead = reverse_list_recursive(current); current->next = parent; printf("\n %d %d \n",current->value,parent->value); return newhead.

I get the same output after I made the modifications – ravi Nov 2 '10 at 15:09.

Some problems I could see: You need to make the next pointer of the new last node NULL. You existing function will blow if I pass NULL to it initially.

I was seeking a solution to solve the first problem ... – ravi Nov 2 '10 at 15:10.

I don't see the benefit of recursion here, iteration will work just as well. It's been forever since I've written C (and no easy way to test the following for syntax errors... or cringe core dumps, but you get the idea). Node *reversed_list(node *list) { node *fwd=list;//Purely for readability node *last=null; node *next=null; node *rev=null; do { //Cache next next=fwd->next; //Set current rev=fwd; //Reset next to point back rev->next=last; //Update last last=fwd; //Forward ptr; fwd=next; } while (fwd!

=null); return rev; } Pretty sure your *list is useless after you've called this since it's now pointing to last element of the list which has ->next=null, could just update that instead of returning the pointer. Update (for recursive solution) As others have said, your new tail is messed up (points back at the last element, but should point to null)... and you don't return the correct head, you return the second element. Consider the list a->b->null with your algorithm: p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a return a; //a->b, b->a, a returned //But what you wanted is a->null, b->a, and be returned The following updated code will fix: node *reverse_list_recursive(node *list) { node *parent = list; node *current = list->next; if(current == NULL) return parent; else { current = reverse_list_recursive(current); current->next = parent; parent->next=null; //Fix tail printf("\n %d %d \n",current->value,parent->value); return current; //Fix head } } With list a->b->null: p=a, c=b; c= p=b c=null return b; //b->null c=b c->next=a //b->a p->next=null //a->null return b; // b->a->null.

I got the solution using iteration. I was experimenting recursion ... – ravi Nov 2 '10 at 15:16 Fair enough {might want to mention that in question next time}, I've added updated recursive approach (two minor changes for the new head and new tail) – Rudu Nov 2 '10 at 15:48.

Here goes recursive code to reverse a linked list . List * reverse(list * head) { if(head == NULL || head -> link == NULL ) return head; list *node = reverse(head- > link ); head ->link -> link = head; head -> link = NULL; return node ; }.

Severl versions above are not working as OP wanted, so here is my recursive version tested fine: node * reverseRecursive(node *p,node **head) { if(p->next == NULL) { *head = p; return p; } node *before; before = reverseRecursive(p->next,head); before->next = p; p->next = NULL; return p; } //call from main node*head; //adding value //assuming now head is now 1->2->3->4->NULL node* newHead; reverseRecursive(head,&newHead); //now now newHead is now 4->3->2->1->NULL.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.