Reverse a Linked List Recursively

Leetcode-206 Reverse Linked List Difficulty: Easy

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Source: Leetcode

ALERT, ALERT, ALERT !!!

If you have come to see the solution before trying to solve it yourself, this really won’t help you, promise! If that is the case, we will recommend, please go back and first try it yourself. If you can’t solve it after (at least)an hour of thinking and trying, please come back! 🙂You can solve it here

__________________________________________________________

Recursive Solution

Let’s consider we have a linked list like below. A single node of list has 1) a value part and 2) a pointer that points to the next element.

A separate head pointer points to node A, next pointer of A points to B and so on. Finally, D is the last element of list, so, it points to NULL. After the list is reversed, D will be the first element and A will be the last element.

The idea of recursive solution is, we will traverse forward from A to D, then will return D and traverse backward to A. During the backward traversal, we will change each pointer’s direction so that they point to their respective previous element. For example, D will point to C, C will point to B and so on. Finally, being the last element, node A of the reversed list will point to NULL. So, let’s see how the recursive algorithm will work as we traverse forward and then backward.

Forward Traversal

The above image shows how forward traversal will look like for each step from A to D. Each recursion call creates a stack frame for the local variables. So, in step-1, A will be stored in stack, then B in step-2, then C and so on. Finally, D points to NULL, so there will be no more recursive calls. Instead, D will be returned. In the code, this is like:

if (head->next == NULL) return head; // in case of D, head = D

Backward Traversal

Returned value of D will be received by C. For that, we will use a variable named tail. From C, this will be returned to B. So, ultimately C is returning D to B. Similarly, B will return D to A, and finally A will also return D to the caller of recursive function. This way, we will receive D as the head of the reversed linked list.

Now, for each node, before returning D to it’s previous node, some magic will happen! Let’s take C for example. Before returning D to B (using tail variable), C will make D to point back to C. Formally, we need to do C->next->next = C and then C->next = NULL. In code, this is like:

head->next->next = head; head->next = NULL;

Let’s see how the backward traversal will work visually.

Backward Traverse – D to C

Backward Traverse – C to B

Backward Traverse – B to A

Final List

Code

class Solution {
public:
    ListNode* rec(ListNode* head) {
        if(head->next == NULL)
            return head;
        ListNode* tail = rec(head->next);
        head->next->next = head;
        head->next = NULL;
        return tail;
    }
    
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head;
        return rec(head);
    }
};

Thanks for reading. Please let us know if any part of this tutorial is hard to understand. Comment if you like it, hate it or want to suggest for improvement.

Happy Coding ! 😀