Jun 122012
 

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 Responses to “Recursive function to reverse a linked list”

Comments (2)
  1. 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

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=""> <s> <strike> <strong>

(required)

(required)