Reversing a Singly Linked list
June 12, 2012
const keyword in CPP
June 12, 2012

Recursive function to reverse a linked list

Earlier I talked about Reversing a Singly linked list without using recursion. Today let’s write a recursive function to reverse a singly linked list.

Note, that Recursion comes with its own cost. to learn more, see this post…

Solution

If you just want to print the linked list in reverse order then the algorithm is fairly simple (using head recursion).

void printReverse(Node* head)
{
    // terminating condition
    if(head == NULL)
        return;
    printReverse(head->next);
    printf("%d ", head->data);
}

But the above function does not change the structure of the linked list, it just print it in reverse order. So it is not reversing the linked list but just printing it. (We have already covered this topic earlier)
Function to reverse will also be on the same lines.

void recursiveReverse( Node** head)
{
    Node* first;
    Node* rest;
    if (*head == NULL)
        return;
    first = *headRef;       // suppose first = {1, 2, 3}
    rest = first->next;  // rest = {2, 3}
    if (rest == NULL)
        return;
    recursiveReverse(&rest);
    first->next->next = first;
    first->next = NULL;
    *head = rest;
}

2 Comments

  1. deepika says:

    For reversing the linked-list code, I think the head will point to the 2nd element in the input list.
    Please correct me if i am wrong.

Leave a Reply to Anonymous Cancel reply

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