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;
}