Reverse Linked List

Ah! a classic. Suppose we have a linked list:

1 → 2 → 3 → 4 → null

To reverse this list, we do not need to change the nodes or their sequences or move them. In fact, there is no such thing as moving a node. The key idea of reorganizing a linked list in any way comes down to changing the direction of each next pointer.

So, we expect:

null ← 1 ← 2 ← 3 ← 4

How do we do this? Simple. Make every node’s next point to its previous.

That means we've got one extra variable to maintain. What about next? If we change node.next without remembering where the next node was, we lose the rest of the list.

So it’s gonna be like:

prev ← curr → next → ... → null

Let’s hit the code.

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;  // first node becomes the tail
  
  while (head) {
    const tempNext = head.next;
    head.next = prev;  // reversing direction of next
    prev = head;       // moving prev forward
    head = tempNext;         
  }      
  return prev; // new head / first node
}

This was pretty easy. But before I could call it a day, I read LC say this:

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

"Recursion" huh? Hmmmm. Let's tackle this one.

The Recursive Way

Now how do I start thinking about this? In a recursion problem I usually start by defining the base case, asking: "What is the smallest subset of this problem that can be solved without any work?"

In this case, "what is the smallest list that can solve itself?" Well, a single node linked list is always its own reverse. That’s our base case.

// base case
if (!head?.next) return head;

This case will always be a reverse of itself. Now the core idea that forms here is that the inner function call is trusted to always return the head of the reversed linked list.

The outer function’s local job is to take the head sitting outside that reversed list and attach it to the end of the reversed smaller list so the overall result is still correctly reversed.

Look at this example:

// inner call returns (head: 4)
4 → 3 → 2 

// outer head
1

// we take the outer head and place at the end of the list
4 → 3 → 2 → 1

It looks simple but is bug-prone if we don’t think through the code. Let’s start coding.

function reverseList(head: ListNode | null): ListNode | null {
  // empty and single node lists are always their own reverse
  if (!head || !head.next) return head; 
  
  // storing the smaller reversed list
  const reversedHead = reverseList(head.next);
  // we trust the above call to always return a correctly reversed head 
  // as long as I (this function) does its job right
  
  // My job: take my local head and attach it at the tail
  // Do I have a link to the tail? 
  // ...  
}

If you pay attention, at every step the tail of the reversed list will be the same as the next of the outer head. Let's do a simulation.

For:

1 → 2 → 3 → 4

The recursion eventually reaches 4 and returns 4.

When we're back at 3, we have:

outer head: 3
returned list: 4 → null

Notice that 3 already has a 4 which is currently both the head and the tail of the returned reversed list. For now, just attach 3 at the end of the returned list and move forward.

Next, we have:

2 | 4 → 3 → null

Let’s count how many links we have within this call:

head → 2
reversedHead → 4
4.next → 3 
2.next → 3

So, we have a link to the outer head, one to the reversed head, and two more links to the tail of the reversed list. Notice the pattern: the outer head will always have a link to the inner tail.

So conceptually:

head.next.next = head  // head.next is the tail and we attach head at tail's next
head.next = null

Now the final solution:

function reverseList(head: ListNode | null): ListNode | null {
  if (!head?.next) return head;

  // every call is trusted to return a reversed sub-list
  const reversedHead = reverseList(head.next);

  // head still points to the new tail of the reversed list
  head.next.next = head;
  head.next = null; // head becomes tail
  
  return reversedHead;
};

So for the above example, the call stack roughly looks like:

reverseList(1)
  reverseList(2)
    reverseList(3)
      reverseList(4)
        return 4
      make 4 → 3
      return 4
    make 3 → 2
    return 4
  make 2 → 1
  return 4

And that’s cracked. Another problem solved.