Level 2 · 30 min

Linked Lists: Pointer Manipulation Patterns

Linked lists are simple in theory but a minefield in practice — every interview-quality bug lives at a pointer boundary. CLRS chapter 10 covers the data structure; Cracking the Coding Interview chapter 2 contains the full taxonomy of patterns: dummy head, runner, in-place reversal, and Floyd''s cycle detection.

The Dummy Head Trick

Every pointer manipulation that may modify the head node should use a sentinel/dummy node. Without it, you write a special case at the top of every method (''if (head == target) head = head.next''). With a dummy: Node dummy = new Node(0, head); ... return dummy.next. The dummy never holds real data; it exists so that prev.next = curr.next works uniformly even when prev IS the conceptual ''before head'' position. CTCI ch. 2 problem 2.1 (remove duplicates) and 2.5 (sum lists) both become 30% shorter with a dummy. Cost: one extra allocation per call — negligible for the bug surface saved.

The Runner / Two-Pointer Patterns

Two pointers traversing at different speeds solve a category of problems in one pass: (1) Find middle of list — slow advances 1, fast advances 2; when fast hits null, slow is at the middle. (2) Cycle detection (Floyd''s tortoise-and-hare) — if there is a cycle, fast eventually meets slow inside the cycle. CLRS exercise 10.2-7 covers this; the meeting-point math (Floyd''s lemma) lets you find the cycle entry. (3) Find Kth-from-end in one pass — advance fast K steps first, then advance both until fast hits null; slow is at the answer. (4) List intersection — two pointers walk both lists, switching to the other list when reaching null; they meet at the intersection or both at null. Each is O(n) time, O(1) space.

In-Place Reversal

Reverse a singly-linked list in place by walking three pointers: prev=null, curr=head, next=null; while (curr) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev. Get this wrong and you create a cycle (curr.next pointing to itself) or lose the tail (forgot to save next before overwriting). The pattern generalizes: reverse a sublist between positions m and n (CTCI 2-style) by reversing the m..n range and stitching back. Critical edge cases: empty list (head=null returns null), single node (no reversal needed), reversing across head (use a dummy). Recursive reversal exists but uses O(n) stack — can stack-overflow on a 100K-node list, so prefer iterative.

Key Takeaways

Always use a dummy head when the head may change. Eliminates 70% of pointer bugs.
Two-pointer (slow/fast) patterns: middle, cycle detection, Kth-from-end, intersection — all O(n) time, O(1) space.
Iterative reversal (prev/curr/next) only. Recursive recursion-stacks on long lists; you will see StackOverflowError in production.

Code example

// Java — Floyd's cycle detection + entry point
static Node detectCycleEntry(Node head) {
  Node slow = head, fast = head;
  // Phase 1: detect cycle
  while (fast != null '&'&' fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) break;       // cycle confirmed
  }
  if (fast == null || fast.next == null) return null; // no cycle
  // Phase 2: find entry. Reset one pointer; both advance 1 step until they meet.
  slow = head;
  while (slow != fast) { slow = slow.next; fast = fast.next; }
  return slow;                       // cycle start
}

// In-place reversal — three-pointer dance
static Node reverse(Node head) {
  Node prev = null, curr = head;
  while (curr != null) {
    Node next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}