Reversing a singly linked list using recursion aka Recursively link reversal

The code to reverse a singly linked list using iteration is trivial, using the three pointer method. Lets have a look at the method to reverse a linked list recursively. Not only this is fast, but clears your pointer concepts if you think it cleanly.

Lets define the function.

It would be something like this:

Node* reverseList(Node** head)


This means we are passing the address of the pointer pointing to the head node. We do so, because this is where we want to store the return address. Every time we recurse, we do the following:


1. store the current head in a new variable called now.
2. check if we are at the end of list
3. if we are, we just return
4. if we arent, we collect the newhead from the rest of the list
5. we point the now->next->next  (now which we stored in 1) to now.
6. we make now->next = NULL.

  Node* reverseList(Node **head) {
if (*head == NULL)
return NULL;
Node *now = *head;
Node *newhead = NULL;
if((*head)->next == NULL)
return *head;
else
newhead = reverseList(&((*head)->next));
now->next->next = now;
now->next = NULL;
return newhead;
}


Lets consider an example 1->2->3->4->NULL


Call 1:
*head points to 1
saved *head into now, so now points to 1
newhead = NULL
enter the else, recurse, i.e. reverseList(2)


Call 2
*head points to 2

saved *head into now, so now points to 2

newhead = NULL

enter the else, recurse, i.e. reverseList(3)

Call 3

*head points to 3

saved *head into now, so now points to 3

newhead = NULL

enter the else, recurse, i.e. reverseList(4)

Call 4

*head points to 4

saved *head into now, so now points to 3

head->next = NULL

enter the if, return from Call 4

Return into Call 3

newhead now stores *head = 4

now = 3

now->next = 4

now->next->next = now  means we set  3 <- 4

now->next = NULL  means we set NULL <- 3 <- 4

return newhead, i.e. 4

Return into Call 2

newhead now stores  4

now = 2

now->next = 3

now->next->next = now  means we set  2 <- 3 <- 4

now->next = NULL  means we set NULL <- 2 <- 3 <- 4

Return into Call 1

newhead now stores  4

now = 1

now->next = 2

now->next->next = now  means we set  1 <- 2 <- 3 <- 4

now->next = NULL  means we set NULL <- 1 <- 2 <- 3 <- 4

we return newhead