Reversible reverse list

Question

I have a Node defined on the Linked List as:

typedef struct abc { int id; struct abc *next; }node; 

I want to recursively cancel the linked list. I pass a pointer to the head of the function. The definition of my function is as follows:

 node *reverseLinkedListRecursively(node *head) { node *current; node *rest; if(head == NULL) return head; current=head; rest=head->next; if(rest == NULL) { return rest; } reverseLinkedListRecursively(rest); current->next->next=rest; current->next=NULL; return rest; } 

How do I proceed? I have implemented an iterative approach.

Answer 1

It should work as follows:

 node *reverseLinkedListRecursively(node *rest, node *reversed) { node *current; if (rest == NULL) return reversed; current = rest; rest = rest->next; current->next = reversed; return reverseLinkedListRecursively(rest, current); } 

First run it with

 reverseLinkedListRecursively(linkedList, NULL); 

BTW: this function is tail recursive. Therefore, a modern compiler should be able to turn this recursive solution into a more efficient iterative solution.

Answer 2

 node *reverseLinkedListRecursively(node *head) { node *current; node *rest; if(head == NULL) return head; current=head; rest=head->next; if(rest == NULL) { /* Wrong. Think about the simple case of a one-element list. Your code will return NULL as the reversed list. */ //return rest; return current; } /* You lost the return value, which will be the beginning of the reversed 'rest'. */ //reverseLinkedListRecursively(rest); rest = reverseLinkedListRecursively(rest); /* current->next points to the last element in the reversed 'rest'. What do you want that to point to? */ //current->next->next=rest; current->next->next = current; // temporarily circular current->next=NULL; /* Now you can return rest, since you set it to the beginning of the reversed list. */ return rest; } 

Answer 3

In order to recursively cancel a linked list, we reverse (recursively) a sub-list consisting of everything except the first node, and then put the first node at the end. To put the first node at the end, we need a recursive call to return a pointer to the last node so that we can access its next member. We stop recursion when the sublist is null, and simply return the current node. After we attach the first node to the end of the recursive call results, the first node is the “last node” when we return from the current recursive call. There is one final detail: the initial first node (now the last) will still point to the second second node (now the second-last). We need to fix this as null, since now this is the end of the list.

In this way:

 node* reverseLinkedListHelper(node* head) { if (head->next == NULL) { return head; } node* last = reverseLinkedListRecursively(head->next); last->next = head; return head; } void reverseLinkedList(node* head) { assert (head != NULL); reverseLinkedListHelper(head); head->next = NULL; } 

There is another problem that I’ll think about: how do we get a pointer to the new list head? :)

Answer 4

For each recursion, keep track of the current node and the front of the rest of the node. Come back when the rest is NULL. After returning to recursion, cancel the following "rest" field to indicate the current one. To track the new first node, the recursive function simply takes the old node back.

 void recursive_reverse() { // driver for the recursive reverse function. // first is a data member of linked list that point to the first node of list. first = recursive_reverse(first, first->next); } Node* recursive_reverse(Node *current, Node *rest) { // if rest == NULL, the current must be the old last node, // which is also the new first node if (rest == NULL) return current; Node *new_first = recursive_reverse(current->next, rest->next); // rearrange pointers rest->next = current; current->next = NULL; // pass along the new first node return new_first; } 

My initial implementation uses a clock node, so I have not tested the code here. Sorry Just read it as pseudo code.

Answer 5

 void RecursiveReverse(struct node** headRef) { struct node* first; struct node* rest; if (*headRef == NULL) return; // empty list base case first = *headRef; // suppose first = {1, 2, 3} rest = first->next; // rest = {2, 3} if (rest == NULL) return; // empty rest base case RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case after: rest = {3, 2} first->next->next = first; // put the first elem on the end of the list first->next = NULL; // (tricky step -- make a drawing) *headRef = rest; // fix the head pointer } 

Answer 6

If you want to cancel the list, you must have the node pointers in the node struct:

 typedef struct abc { int id; struct abc *next; struct abc *prev; }node; 

and your list should have pointers to the head and tail:

 typedef struct list { node * first; node * last; } list; 

Answer 7

Hey guys, they will find programs to reverse the linked list with and without recursion, hope this helps you.

 LINK *reverse_linked_list_recursion(LINK *head) { LINK *temp; if (!head) { printf("Empty list\n"); return head; } else if (!head->next) return head; temp = reverse_linked_list_recursion(head->next); head->next->next = head; head->next = NULL; return temp; } LINK *reverse_linked_list_without_recursion(LINK *head) { LINK *new, *temp; if (!head) { printf("No element in the list\n"); return head; } else { new = head; while (head->next) { temp = head->next; head->next = temp->next; temp->next = new; new = temp; } } return new; }