Reversing a Singly Linked List

1. Brute-Force: Reversing with a Stack

When first approaching this problem, a natural thought is to use an auxiliary data structure that can reverse the order of elements for us. The stack, with its Last-In-First-Out (LIFO) behavior, is perfectly suited for this.

The idea is simple:

1. Traverse the linked list from head to tail, pushing the value of each node onto a stack.
2. Once all values are in the stack, traverse the list again from the head.
3. For each node, pop a value from the stack and overwrite the node's current value.

Because of the LIFO principle, the last value we pushed (from the tail of the list) will be the first one we pop, effectively reversing the sequence of values in the list.

Let's watch a short explanation of this approach.

While this method works, it has two significant drawbacks for an interview setting:

• Space Complexity: It requires O(n) extra space for the stack, where n is the number of nodes in the list.
• Pointer Invariance: It doesn't actually reverse the list structure; it just shuffles the data within the existing nodes. An interviewer will almost always expect you to modify the pointers themselves.

This brute-force solution is a good starting point, but let's move on to the more efficient, in-place method.

2. The Optimal Iterative Approach: The Three-Pointer Technique

To reverse the list in-place without using extra space, we need to change the direction of the next pointers of each node. A node that points forward to its successor must be rewired to point backward to its predecessor.

The main challenge here is that as soon as you change a node's next pointer (e.g., current.next = prev), you lose the link to the rest of the original list. To prevent this, we use a classic three-pointer strategy:

1. prev: Tracks the node that comes before the current node in the reversed sequence. It starts as null because the original head will become the new tail, pointing to nothing.
2. temp (or current): This is our main traversal pointer, iterating through the list one node at a time. It starts at head.
3. front (or nextTemp): This pointer "scouts ahead" and stores a reference to the next node in the original list before we break the link.

The process for each node is a four-step dance:

1. Save the next node: front = temp.next.
2. Reverse the link: temp.next = prev.
3. Move prev one step forward: prev = temp.
4. Move temp one step forward: temp = front.

We repeat this until temp becomes null. At that point, prev will be pointing to the new head of the reversed list.

The diagram below illustrates this step-by-step pointer manipulation.

To see this in action, the following video provides an excellent animated dry run.

Now, let's consolidate this with a reading that presents the formal algorithm and a clean Java implementation.

This iterative solution is highly efficient, with a time complexity of O(n) and a space complexity of O(1), making it the preferred solution in most interview scenarios.

3. The Recursive Approach

Recursion offers another powerful way to think about this problem. The core idea is to apply a "leap of faith": assume you can reverse the rest of the list, and then figure out what to do with the current node.

Here's the recursive logic:

• Base Case: If the list is empty (head == null) or has only one node (head.next == null), it's already reversed. Return head.
• Recursive Step:
  1. Call the reverseList function on head.next. This call will recursively reverse the entire sublist that starts after the head and, crucially, will return the newHead of that reversed sublist (which is the original tail of the list).
  2. Now, the head node is still pointing to its original successor. Let's call this front = head.next. In the reversed sublist, front is now the last node, and its next pointer is null.
  3. We need to attach head to the end of this reversed sublist. We do this by setting front.next = head.
  4. Finally, we must set head.next = null. This makes the current head the new tail and prevents a cycle in the list (a very common bug!).
  5. Return the newHead that was returned by the initial recursive call.

This can be tricky to visualize. The image below shows how the problem is broken down recursively and then reassembled.

The following video provides an exceptionally clear dry run of the recursion, showing how the call stack manages the state at each step.

For a final review, let's look at the code and a concise summary of the logic.

The recursive solution has a time complexity of O(n), same as the iterative one. However, its space complexity is O(n) due to the recursive call stack depth. While elegant, the iterative solution's O(1) space usage makes it superior in memory-constrained environments.

As promised, here is the link to the problem on LeetCode. I highly recommend you try to implement both the iterative and recursive solutions yourself.

• LeetCode 206: Reverse Linked List

Conclusion

You have now learned and analyzed three different ways to reverse a singly linked list. This is a significant milestone that solidifies your command over pointer manipulation.

Key Takeaways:

• Brute-Force (Stack): An intuitive but space-inefficient approach that only modifies data, not pointers. Time: O(n), Space: O(n).
• Iterative (Three-Pointers): The most optimal solution. It reverses the list in-place by carefully re-wiring next pointers. Time: O(n), Space: O(1).
• Recursive: An elegant solution that demonstrates a deep understanding of recursion. It solves the problem by breaking it down, but at the cost of space. Time: O(n), Space: O(n).
• Interview Context: In an interview, you should be able to explain all three, starting with the brute-force idea, and then coding the optimal iterative solution. Being able to also code the recursive one is a huge plus.

In our next lesson, we will explore another powerful linked list pattern: the slow-fast pointer technique. This will enable us to solve problems like finding the middle of a linked list efficiently.