c++data-structureslinked-list

How does reversing a Linked List using recursion work?


I am looking for an explanation on how reversing a linked list using recursion works.
The code is given below but I am not able to figure how it works.

ListNode* reverseListRecursive(ListNode* head)
{
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *temp = reverseListRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return temp;
}

Solution

  • A list of nil is it's own reverse.

    A list of head -> nil is also it's own reverse.

    A list of head -> tail has a reverse that is reverse(tail) followed by head. The first element of tail will be at the end of reverse(tail), and head->next still points to that element after you reverse(tail), so you can put head at the end by following head->next->next.