Iterative Singly Linked List Reversal

Hello! In our previous lesson, we saw how a dummy node can elegantly handle operations at the head of a linked list, eliminating pesky edge cases. This pattern is a powerful tool for problems involving insertion or deletion at the start of a list.

Today, we'll dive into another cornerstone linked list problem: reversing the entire list. This operation is a classic test of pointer manipulation. While you could solve it using a dummy node and a "head insertion" strategy, we will focus on the most common and direct iterative approach: an in-place reversal using three pointers. Mastering this technique will sharpen your ability to reason about and transform data structures without allocating new ones, a valuable skill for any developer.

By the end of this lesson, you will be able to reverse a singly linked list iteratively, ensuring you don't lose track of the rest of the list as you rewire each node's next pointer.

The Core Challenge: Reversing Pointers In Place

Imagine a list: 1 -> 2 -> 3 -> NULL. Our goal is to make it 3 -> 2 -> 1 -> NULL. This means that for each node, its next pointer must be redirected to point to its predecessor.

This presents two immediate problems:

1. In a singly linked list, a node has no reference to its predecessor. How do we know what node.next should point to?
2. Once we change node.next (e.g., make node 2 point to node 1), we lose our link to the original next node (node 3). The rest of the list is effectively lost.

The solution lies in carefully orchestrating a few pointer variables to keep track of everything we need at each step.

The Three-Pointer Technique

To solve this, we'll iterate through the list, and at each node, we'll perform the reversal. We need three pointers to manage the state during this process:

• previous: This will track the node that comes before the current node. As we build the reversed list, this pointer will hold the head of our reversed portion. It starts as null, because the original head's new next will be null.
• current: This is the node we are currently visiting and whose next pointer we intend to reverse. It starts at the head of the list.
• next: This is a temporary pointer. Its crucial job is to save a reference to the original next node of current before we perform the reversal. This is the key to preserving the unprocessed suffix of the list.

The process is a loop that continues as long as current is not null. Inside the loop, we perform a four-step "dance" to reverse one node and advance our pointers.

The following image provides a static, step-by-step visualization of this process. The pointers are named differently (Pointer1, Head, Pointer2), but they map directly to our previous, current, and next pointers, respectively.

To see this pointer dance in action, the following video provides an exceptionally clear and detailed walkthrough. Pay close attention to how the state of the previous, current, and next pointers changes with each iteration.

The Reversal Algorithm

As you saw in the video, the logic inside the while loop can be broken down into a repeating sequence. A helpful way to remember this is to think of it in three phases, as described in the article "Reversing a Linked List" on dev.to.

For each current node:

1. Store the Suffix (Save next): Before changing any pointers, we must save current.next so we don't lose the rest of the list.
   let next = current.next;
2. Perform the Reversal: Change current.next to point to the previous node.
   current.next = previous;
3. Advance the Pointers: Move previous and current one step forward for the next iteration.
   previous = current;
current = next;

This loop continues until current becomes null, meaning we've processed every node. At this point, the previous pointer will be holding the last node we processed, which is the new head of the reversed list.

Implementation and Common Pitfalls

Now, let's look at the full implementation in TypeScript. It's surprisingly concise. The key is the precise order of operations inside the loop.

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}

function reverseList(head: ListNode | null): ListNode | null {
  let previous: ListNode | null = null;
  let current: ListNode | null = head;

  while (current !== null) {
    // 1. Store the next node before we overwrite current.next
    const next: ListNode | null = current.next;

    // 2. Reverse the current node's pointer
    current.next = previous;

    // 3. Move pointers one position ahead for the next iteration
    previous = current;
    current = next;
  }

  // After the loop, 'previous' is the new head of the reversed list
  return previous;
}

Getting the pointer updates in the wrong order is the most common mistake when solving this problem. The following resource provides another look at the implementation and, crucially, highlights these common pitfalls.

As the article notes, this algorithm runs in $O(n)$ time, as we visit each node once. The space complexity is $O(1)$ because we only use a few extra pointers, regardless of the list's size.

An Alternative Perspective

It's worth noting that the "head insertion" strategy we saw with dummy nodes in the last lesson can also be used here. You can think of the iterative reversal as taking nodes one by one from the original list and prepending them to a new, growing list (which is tracked by the previous pointer).

The author of the dev.to article "Reversing a Linked List" had a great insight: the goal isn't really to reorder nodes, but simply to reverse the direction of the pointers.

Conclusion

You've now learned one of the most fundamental linked list algorithms. The three-pointer iterative reversal is a pattern that demonstrates precise control over a data structure's pointers, and it's a common building block for more complex list problems.

Here are the key takeaways:

• The Three Pointers: The iterative reversal is orchestrated by three pointers: previous, current, and next.
• Preserving the Suffix: The most critical step is storing current.next in a temporary next variable before modifying any pointers. This prevents you from losing the rest of the list.
• The In-Place Swap: The core of the loop consists of reversing the pointer (current.next = previous) and then advancing the pointers (previous = current, current = next).
• New Head: After the loop terminates, previous points to the new head of the reversed list.

In our next lesson, we'll explore another classic pointer manipulation pattern: the slow and fast pointer technique. We'll use it to solve a completely different kind of problem: detecting if a linked list contains a cycle.