Reverse a Linked List using Recursion

Problem: To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion”.

Solution:

In recursive approach, we need to move to the end of the node. But must stop just before the end of the node, and we should have total 3 nodes in hand.

head is what is in the stack. head->next->next will always be NULL. If it is not NULL, recursion continues. This is the base condition for our recursion.

If there is only one node, there is no need to reverse the list. So, its ok to check for head and head next both being non-NULL are not. If any one of it becomes NULL, we can return the head recorded.

```void recursiveReverse(struct node** head_ref)
{
struct node* first;
struct node* rest;

/* empty list */
return;

rest  = first->next;

/* List has only one node */
if (rest == NULL)
return;

/* put the first element on the end of the list */
recursiveReverse(&rest);
first->next->next  = first;

/* tricky step */
first->next  = NULL;

/* fix the head pointer */
}
```

9 Thoughts on “Reverse a Linked List using Recursion”

1. can u illustrate the above problrm solution with an example

2. P. Alpagut on April 4, 2014 at 10:20 pm said:

Thank you for the question. I thought about different solution;

Node* reverseList(Node* head, Node* prevNode = NULL)
{

{

if(temp != NULL)
{
}
}

}

3. Shivaprabhu T H on June 30, 2014 at 8:17 am said:

@ P. Alpagut it returns the head as address of revrsed last node i.e adress of 1st node of normal list . so to print the list again we hav to travrse from end

4. codecrush on July 22, 2014 at 8:17 am said:

Can you please compare this with the one you stated above.
Problems: One for sure that is traversing after reversing the list.

Reverse(Start->Next,Start);
Start->Next = null;

Reverse(Node* current, Node* previous)
{
if(current->Next != null)
Reverse(current->Next, current);
current->Next = previous;
}

5. Guillaume on October 22, 2014 at 9:16 pm said:

In java:

ListElement reversed = reverse(tail);
return reversed;
}

6. Ambarish Rapte on April 1, 2015 at 4:24 pm said:

Here is another way of it…

void ReverseTheList(Node<T>* ptr)
{
if(ptr->getNext()) {
ReverseTheList(ptr->getNext());
}
else {
return;
}
ptr->getNext()->setNext(ptr);
}

void ReverseTheList()
{
t->setNext(NULL);
}
}

7. void reverse(Node *par, Node *next, Node **root){
if(par == NULL){return;}
if(next==NULL){
*root = par;
return;
}
reverse(next,next->next,root);
next->next=par;
par->next=NULL;
}

8. //no need to traverse from the end
If (head == null) return null;
}

Public ListNode reverseListRecursiveHelper(ListNode head, ListNode prevNode){
If (nextNode == null) return head;
}

9. public static NodeSLL reverseRecursion(NodeSLL ll){
if(ll==null) return ll;
return reverseRecursionHelper(null, ll);
}

private static NodeSLL reverseRecursionHelper(NodeSLL prev,NodeSLL curr){
if(curr==null) return prev;
NodeSLL next = curr.next;
curr.next = prev;
NodeSLL r = reverseRecursionHelper(curr, next);

return r;

}