Reversal & Fast/Slow Pointers

Two techniques in this chapter both appear constantly in real linked-list problems: reversing a list in place, and moving two pointers through the same structure at different speeds.

Reversing a list means every node's next reference has to flip direction, pointing at whatever used to come before it instead of after. Since a singly linked list offers no way to walk backward, doing this without a second data structure means walking forward exactly once while carefully rewiring each node before losing the only reference to the rest of the chain.

Tracing it on a tiny list, 1 -> 2 -> 3 -> None: start with prev = None and current = node(1). Save next_node = node(2), then point node(1).next at prev (None), then advance prev to node(1) and current to node(2). Save next_node = node(3), point node(2).next at node(1), advance prev to node(2) and current to node(3). Save next_node = None, point node(3).next at node(2), advance prev to node(3) and current to None - the loop ends. The new head is prev, node(3), and the chain now reads 3 -> 2 -> 1 -> None.

• -Three pointers are in play at every step - prev, current, and next_node - never more, never fewer.
• -next_node is always saved before current.next is overwritten, which is exactly what keeps the rest of the unreversed list from being lost.
• -The whole operation is O(n) time and O(1) extra space - no new nodes or lists are created, only existing ones re-pointed.

A related but distinct pointer trick runs two pointers through the list at different speeds: slow advances one node per step, fast advances two. If the list has no cycle, fast simply reaches the end (None) first and the search concludes cleanly. If the list does have a cycle - some node's next reference loops back to an earlier node instead of ever reaching None - fast eventually laps slow, and the two pointers land on the exact same node, proving a cycle exists without needing any extra memory to track which nodes have already been visited.

This technique is commonly called Floyd's cycle detection, or "the tortoise and the hare." The same fast/slow idea generalizes well beyond cycle detection - for instance, finding a linked list's midpoint in a single pass, since the moment fast reaches the end, slow is sitting exactly at the middle. It is worth remembering as a preview of the broader two-pointer pattern, which gets its own full module later in this tier.