Reverse Linked List Recursively: Easy Explanation

Let’s explain the reverseList function, which reverses a singly-linked list, step by step:

(follow the code-article-code-repeat process to understand better)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* restOfList = reverseList(head->next);
 //1. base case/ last return storing teqnique
        // 2. using recursive process reversly / when returning

        // Reverse the pointers
        head->next->next = head; // 3 no node
        head->next = nullptr; // we are deleting the current head next, because we will put the node before that
        //in its next on next recursive call

        return restOfList; 
        // we return this, because it will always returnt he last ending value, which is the
        // base case return value and we need the last head.
    }

1. Base Case: The first thing the function checks is whether the head is either nullptr or it has no next node (head->next is nullptr). If either of these conditions is true, it means the linked list has only one node or is empty. In such cases, there is nothing to reverse, so the function directly returns the head node.
2. Recursive Reversal: If the head is not nullptr and there are more than one nodes in the linked list, the function enters the recursive part.

• It calls reverseList(head->next) recursively, passing the next node of the current head. This recursive call effectively reverses the rest of the linked list starting from the node after the current head.
• The recursive calls continue to happen until we reach the last node in the original linked list.

3. Reverse Pointers: After the base case is reached, the function starts executing the reverse process.

• When the function begins returning from the base case (i.e., the recursive calls start to unwind), it reaches the lines:

head->next->next = head;

head->next = nullptr;

These two lines reverse the direction of the pointers in the linked list. They make the next pointer of the node after head point back to head, effectively reversing the order of the nodes. At this point, the current head becomes the new tail of the list.

4. Return New Head:

Finally, the function returns the restOfList, which is the head of the newly reversed linked list. This is the last head node that was the original tail node before the reversal process.

It uses the recursive stack to reverse the order of the nodes in a “bottom-up” manner. The process of the linked list reversal is primarily achieved by changing the pointers between the nodes.