Iterative Singly Linked List Reversal

Welcome to our new module on linked lists. In the previous module, we mastered several powerful patterns for arrays and strings, like sliding windows and two-pointers, which primarily rely on manipulating indices. Now, we shift our focus to a new data structure where relationships are defined by explicit pointers or references rather than sequential positions in memory.

This lesson marks our first step into linked list algorithms. Our goal is to reverse a singly linked list iteratively. This is a fundamental skill in its own right and a building block for solving more complex list-based problems. We'll focus on the precise pointer manipulations required to perform this operation efficiently and correctly.

From Array Indices to Node Pointers

In arrays, a "pointer" is often an integer index. To get to the next element, you simply increment the index. Linked lists are different. Each node contains data and a next pointer that holds the memory address of the subsequent node. To traverse, you must follow this chain of pointers.

Reversing a list, therefore, isn't about swapping data values. It's about methodically rewiring these next pointers to point backward.

The following video provides an excellent visual introduction to this concept. It clearly defines the problem and introduces the high-level iterative strategy.

The Three-Pointer Dance

As the video hints, a critical problem arises as soon as we reverse the first node's next pointer: we break the chain and lose our path to the rest of the list. If node1.next now points to null instead of node2, how do we get to node2?

The solution is to use a "three-pointer" technique to keep track of everything we need at each step of the traversal. We'll use:

1. A prev pointer to track the node that came before the current one. This will be what curr.next should point to.
2. A curr pointer for the node we are currently visiting.
3. A temporary next pointer to save a reference to the next node in the original list before we overwrite curr.next.

This setup allows us to safely rewire the curr node's pointer without losing the rest of the list.

The following segment from the same video walks through this pointer manipulation in detail. It's one of the clearest explanations of this algorithm.

To summarize the logic inside the while loop that runs as long as curr is not null:

1. next_temp = curr.next: We first store the next node in the original sequence before we change any pointers. This is the most crucial step.
2. curr.next = prev: We reverse the current node's pointer, making it point to the node that came before it.
3. prev = curr: We update prev to be our current node, as it will be the "previous" node for the next iteration.
4. curr = next_temp: We move to the next node in the original list, which we safely stored in step 1.

After the loop finishes, curr will be null, and prev will be pointing to the last node of the original list, which is now the new head of the reversed list.

Implementation and Complexity

Now that you have a solid grasp of the algorithm's logic, let's look at how it translates into code. Since you have a broad CS background, it's useful to see this pattern across different languages.

As the article notes, this iterative solution is highly efficient:

• Time Complexity: O(N), because we traverse the list exactly once.
• Space Complexity: O(1), because we only use a few extra pointers, regardless of the list's size. All modifications are done in-place.

For someone focused on interview preparation, being aware of common mistakes is as important as knowing the correct solution. One of the most common errors in this specific problem is exactly what we've been highlighting.

Conclusion

In this lesson, we transitioned from array-based thinking to pointer-based manipulation in linked lists. You've learned the most fundamental linked list operation: iterative reversal. This pattern is not just a common interview question but also a sub-routine in more advanced list problems.

Key Takeaways:

• Reversing a linked list involves rewiring next pointers, not moving data.
• The iterative solution uses a "three-pointer" approach (prev, curr, next_temp) to traverse the list while reversing the links.
• The essential step is to save curr.next in a temporary variable before reassigning it, to avoid losing the rest of the list.
• The algorithm runs in optimal O(N) time and O(1) space.

In our next lesson, we will continue exploring pointer manipulation techniques by learning the fast and slow pointer pattern. This powerful technique allows you to solve a different class of problems, such as finding the middle of a linked list in a single pass, without needing to know its length beforehand.