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 (stack) head->next (not null) head->next->next

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.

Now, we connect head->next->next to head. and set head->next to NULL. since, we have pushed the traversed head’s in the stack.

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 */
    if (*head_ref == NULL)
       return;

    first = *head_ref;
    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 */
    *head_ref = rest;
}

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(head != NULL)
    {
    Node* temp = head->next ;
    head->next = prevNode;

    if(temp != NULL)
    {
    return reverseList(temp, head);
    }
    }
    return head;

    }

  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:

    private ListElement reverse(ListElement head) {
    if (head == null || head.next == null) return head;
    ListElement tail = head.next;
    head.next = null;
    ListElement reversed = reverse(tail);
    tail.next = head;
    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 {
    mHead = ptr;
    return;
    }
    ptr->getNext()->setNext(ptr);
    }

    void ReverseTheList()
    {
    if(mHead) {
    Node<T>* t = mHead;
    ReverseTheList(mHead);
    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
    Public ListNode reverseList(ListNode head){
    If (head == null) return null;
    Return reverseListRecursiveHelper(head, null);
    }

    Public ListNode reverseListRecursiveHelper(ListNode head, ListNode prevNode){
    ListNode nextNode = head.getNext();
    head.setNext(prevNode);
    If (nextNode == null) return head;
    Return reverseListRecursiveHelper(nextNode, 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;

    }

Leave a Reply to UI Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation