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

Example case

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

• Recursive Descent: This is the phase where the recursion is "unfolding," meaning the function is making recursive calls and diving deeper into the problem space, moving towards the base case. This corresponds to what you've called the "descending phase."
• Recursive Ascent (sometimes just referred to as "returning" or "unwinding the recursion"): This is the phase where the recursion is "folding back up," meaning the function is now returning from the base case, and the recursive calls are resolving back up the call stack. This corresponds to what you've called the "ascending phase."

Post-Solution Insights

 func(ListNode head){
	 if (head == null || head.next == null) {
    return head;
   }
	 ListNode reversedListHead = reverseList(head.next);
	 return reversedListHead;
 }
 

These two lines of code are crucial because, with them, we can traverse all the way to the end of the linked list, capturing the last node. Then, as we return through each stack frame, we effectively bring this last node back to the first stack frame, where the fully reversed list is returned.