Recursion-Linked Lists
Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
The ‘move’
The main technique for solving this question is:
Two phases of recursion
The first one is descending. Each movement(recursive call) creates a new stack frame.
The second one is ascending. Unwinding the recursion.
Touching the base of recursion
if (head == null || head.next == null) {
return head;
}
ListNode reversedListHead = reverseList(head.next);
This portion of the code makes us go until the end of the linked list.
Example running
Let’s take the stack frame when the head is 4 in ascending phase.
when the head is 4:
when the head is 3:
The code
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode reversedListHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return reversedListHead;
}
