Sweaty Imposter

Linked List Pattern

CodingJunior2 min read · 5 problemsUpdated

Walk and rewire node pointers directly, with a dummy head in front so changes at the start of the list need no special case.

When to Use It

Merging or rebuilding lists, removing a node by position, digit arithmetic on lists, deep copies, and designs that need O(1) moves, like an LRU cache. For cycles and midpoints, use Fast & Slow Pointers; for reversing a list or a segment, use In-Place Reversal of LinkedList.

Classic example: Merge Two Sorted Lists; LRU Cache.

How It Works

A linked list gives up indexing in exchange for cheap splicing. Given a node, you can insert after it or unlink its successor by changing one or two pointers, with nothing to shift. The cost is that you can only move forward one node at a time, and a node is gone for good the moment nothing points to it. Two habits prevent most bugs. First, put a dummy (sentinel) node in front of the head, so the real head is just another node: building a result means appending after a tail pointer, deleting the head works like deleting any other node, and the answer is dummy.next. Second, save curr.next in a variable before you overwrite it.

The core moves are few. Merging walks two lists with one pointer each and links the smaller front after the tail, as in Merge Two Sorted Lists; Add Two Numbers is the same walk with a carry. Removing a node by position uses two pointers with a fixed gap: move a lead pointer n nodes ahead, then advance both until the lead reaches the last node, so the trailing pointer stops just before the node to delete (Remove Nth Node From End of List). Deep copies, like Copy List with Random Pointer, map each original node to its copy so any pointer in the original can be translated. Designs like LRU Cache pair a hash map from key to node with a doubly linked list, where sentinel head and tail nodes make every unlink and insert the same four pointer writes.

Two related patterns cover the rest of the linked list family. When two pointers move at different speeds to find a cycle or a midpoint, use Fast & Slow Pointers. When the task reverses the list or a run of nodes with prev, curr, and next, use In-Place Reversal of LinkedList. Many medium problems chain all three: Reorder List finds the middle with fast and slow pointers, reverses the second half, and merges the two halves node by node. Before writing code, draw a three-node list as boxes and arrows, and trace the empty list and a single node, since that is where pointer bugs hide.

Key Insight

A dummy node in front of the head turns every change at the front of the list into the ordinary case, and saving next before you overwrite it keeps the rest of the list reachable. With those two habits, merging, deleting, and inserting each take a constant number of pointer writes per node, so most problems run in O(n) time with O(1) extra space.

Worked Example

Merge Two Sorted Lists

list1 = [1, 4, 6], list2 = [2, 3, 7]

  1. Compare 1 and 2: link 1 after the dummy. Merged: 1
  2. Compare 4 and 2: link 2. Merged: 1, 2
  3. Compare 4 and 3: link 3. Merged: 1, 2, 3
  4. Compare 4 and 7: link 4. Merged: 1, 2, 3, 4
  5. Compare 6 and 7: link 6. Merged: 1, 2, 3, 4, 6

Result: [1, 2, 3, 4, 6, 7]. list1 runs out after five comparisons, so the rest of list2 attaches in one pointer write, and dummy.next is the head of the merged list.

Templates

// Build a new list: append after a tail pointer.
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (a != null && b != null) {
    if (a.val <= b.val) {
        tail.next = a;
        a = a.next;
    } else {
        tail.next = b;
        b = b.next;
    }
    tail = tail.next;
}
tail.next = (a != null) ? a : b; // attach whatever is left
return dummy.next;

// Delete in place: stop one node before the target, then skip it.
ListNode guard = new ListNode(0);
guard.next = head;
ListNode prev = guard;
while (prev.next != null) {
    if (/* prev.next should be removed */) {
        prev.next = prev.next.next;
    } else {
        prev = prev.next;
    }
}
return guard.next;

Common Pitfalls

  • Overwriting curr.next before saving it, which cuts off the rest of the list.
  • Returning head after an operation that may have removed or replaced it. Return dummy.next instead.
  • Dereferencing null: check node != null before reading node.next, and node.next != null before reading node.next.next, especially at the end of the list and on empty input.
  • Forgetting to attach the leftover nodes after a merge loop, or to append the final carry in list arithmetic.
  • Updating only one direction when unlinking a node from a doubly linked list, so prev and next disagree and later moves corrupt the list.

When It Breaks

  • Lookup by index costs O(n) per call. If the task keeps asking for the k-th element or needs binary search, copy the values into an array first.
  • A singly linked list can't step backward. Walking from the tail or deleting a node you hold without its predecessor needs a doubly linked list, or a trick like copying the next node's value forward.
  • Recursive solutions use one stack frame per node, so a list of 10^5 nodes can overflow the call stack. Prefer iteration when the list can be long.

Variations

  • Dummy head plus tail pointer: Merge Two Sorted Lists, Add Two Numbers, and Partition List build the answer by appending.
  • Fixed-gap pointers: Remove Nth Node From End of List, and rotating a list by k places.
  • Node-to-copy map: Copy List with Random Pointer, or interleave each copy after its original for O(1) space.
  • Hash map plus doubly linked list: LRU Cache and LFU Cache, with sentinel nodes at both ends.
  • Chained with the other list patterns: Reorder List uses Fast & Slow Pointers for the middle and In-Place Reversal on the second half.

Big O

Time
O(n)
Space
O(1)
Each node is visited a constant number of times, and the rewiring needs only a few pointer variables. A hash map from node to copy (deep copies) or from key to node (LRU Cache) adds O(n) space.
Next PatternMath & Geometry