Linked Lists: Rewiring Pointers Without Losing the List

A linked list gives you exactly one power and takes away another. You can splice a node in or out in constant time — once you already hold the node before it — just by reassigning a .next; what you can’t do is jump to the middle, step backward, or even know how long the list is without walking it. Every linked-list problem lives in that trade, and the recurring hazard is mechanical: the moment you overwrite a .next, the rest of the list can vanish unless you saved a reference first.

Reversing a list is the whole hazard in four lines. You can’t set curr.next = prev until you’ve stashed curr.next, or you’ve just cut off everything ahead of you:

ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;  // save the rest of the list BEFORE we overwrite
    curr.next = prev;           // flip this link backward
    prev = curr;                // advance both pointers
    curr = next;
}
return prev;                    // prev is the new head

Nearly every problem in this category is one of three pointer moves applied carefully enough not to drop anything.

Move 1: a dummy head kills the edge cases

Half the bugs in list code come from the head being special — what if you delete the first node, or the list starts empty? A dummy node sitting in front of the real head erases the distinction: you build or splice from dummy.next and return that at the end, and the “what if it’s the head” branch simply disappears. Merge Two Sorted Lists, Add Two Numbers, and Remove Nth Node From End all get shorter the instant you prepend a dummy.

Move 2: fast and slow pointers, on a list

This is the two-pointers idea with the pointers chasing each other down the same list instead of converging from the ends. Advance one pointer two steps for every one step of the other and geometry does your work: when the fast one reaches the end, the slow one is at the middle (Reorder List needs this). For Remove Nth Node, start both pointers at a dummy in front of the head and push the fast pointer n + 1 steps out; hold that gap and when fast falls off the end, slow is sitting on the node just before the nth-from-last — exactly where you need to be to splice it out. (Advance fast only n and slow lands on the target itself, with no handle on its predecessor — the classic off-by-one here.) And on a list with a loop, the fast pointer laps the slow one and they collide — that’s Floyd’s cycle detection, and Linked List Cycle is its home. Find the Duplicate Number is the sneaky one: treat the array as a list where nums[i] points to index nums[i], and the duplicate is exactly the entrance to a cycle.

Move 3: in-place reversal, in chunks

The four-line reversal above is a building block, not just a problem. Reverse Nodes in k-Group reverses the list k nodes at a time; Reorder List reverses the second half and zips it into the first. The trick that makes these tractable is doing the reversal in place with the three-pointer prev/curr/next dance, so you never allocate a second list — you just relink what you already have.

Which move each problem needs

• Dummy head: Merge Two Sorted Lists, Add Two Numbers, Remove Nth Node From End.
• Fast/slow pointers: Linked List Cycle, Find the Duplicate Number, and the middle-finding step inside Reorder List.
• In-place reversal: Reverse Linked List, Reverse Nodes in k-Group, Reorder List (again — most hard list problems combine two moves).
• A hash map instead: Copy List with Random Pointer maps each old node to its clone so the random pointers can be wired on a second pass — the same hashing reflex from array problems.
• A heap: Merge k Sorted Lists keeps the k list-heads in a min-heap and repeatedly pops the smallest.

The one that’s a whole data structure

LRU Cache is the outlier in the set — not a puzzle over a given list but a structure you assemble: a hash map for $O(1)$ lookup whose values are nodes in a doubly-linked list ordered by recency. Touch an entry and it jumps to the front; run out of room and you evict the tail. The doubly-linked part is the point — you need to unlink a node from the middle in constant time, which a singly-linked list can’t do. The map-plus-doubly-linked-list pairing is the standard build for an LRU cache; doubly-linked lists more broadly turn up wherever you must unlink from the middle in $O(1)$ — the intrusive lists in the Linux kernel, the free lists an allocator walks — even where those carry no recency ordering of their own.

What they cost

Almost all of these are a single $O(n)$ walk with $O(1)$ extra space — you’re relinking nodes you already have, not allocating new ones. The exceptions pay for what they do: Merge k Sorted Lists spends $O(\log k)$ per node on its heap, and Copy List with Random Pointer either burns $O(n)$ on a map or drops back to $O(1)$ with an interleaving trick that threads each clone right after its original. So when an interviewer pins you to $O(1)$ space on a list, they’re really asking whether you can get there by pointer surgery instead of copying.

Draw it before you code it

Pointer surgery is the rare place where writing code first is slower than sketching it. I still draw the boxes for anything past a plain reversal — the couple of minutes it costs is cheaper than the debugging session a lost pointer buys, and I trust a diagram over my own confidence once more than two pointers are in play. Two or three boxes with arrows, and a finger on the node you must not lose, will catch the dropped-.next bug before the compiler does. The eleven problems are combinations of three moves — dummy, fast/slow, reverse — each one a matter of keeping hold of the rest of the list while you rewire the front.

References

• NeetCode 150 — Linked List — the eleven problems, in NeetCode’s order.