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;
}
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
.