Chapter 8a — Linked List Problem Patterns

Every linked list problem reduces to: traverse, rewire pointers, use fast/slow, or combine all three.

Pattern Map

Problem Signal	Pattern	Key Technique
Reverse entire list	Iterative 3-pointer	prev/curr/next
Reverse k at a time	Iterative reverse + reconnect	Count k, reverse, recurse/iterate
Find middle	Fast/slow pointer	Stop when fast.next=null
Nth from end	Fast/slow with gap	Advance fast n steps first
Detect cycle	Fast/slow	Floyd's (Ch 5a)
Check palindrome	Find middle + reverse half + compare	Combine middle + reverse
Merge two sorted	Dummy + two pointers	Classic merge step
Deep copy with random pointers	Three-pass or interleaving	O(n) space or O(1) space
LRU Cache	HashMap + doubly linked list	O(1) get + put + evict
Reorder list	Find middle + reverse half + merge alternating	Three sub-problems

Problem 1: Reverse Linked List

Problem: Reverse a singly linked list.
reverseList(1→2→3→4→5) → 5→4→3→2→1
LeetCode 206. Foundation of every linked list problem.

Fully built in Chapter 8. Both iterative (3-pointer) and recursive versions. Know both cold. The iterative version:

javascript

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

What to say in an interview:
"I need three pointers: prev (the reversed portion's head so far), curr (current node being processed), and next (saved reference before I overwrite curr.next). At each step: save next, reverse the pointer, advance both prev and curr."

Problem 2: Merge Two Sorted Lists

Problem: Merge two sorted linked lists.
mergeTwoLists(1→2→4, 1→3→4) → 1→1→2→3→4→4
LeetCode 21. Essential building block.

Built in Chapter 8, Part 10. Key pattern note: dummy node eliminates head-selection logic.

javascript

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 || l2;
  return dummy.next;
}

Complexity: O(n + m) time, O(1) space.

Problem 3: Reorder List

Problem: Given list L0→L1→...→Ln-1→Ln, reorder it to L0→Ln→L1→Ln-1→L2→Ln-2→... in place.
reorderList(1→2→3→4→5) → 1→5→2→4→3
LeetCode 143. Asks you to compose three sub-operations.

Four Questions

Q1: What do I have? A singly linked list.
Q2: What do I want? Alternate elements from front and back, in place.
Q3: What is the brute force? Store all nodes in an array, use two pointers to interleave. O(n) time, O(n) space.
Q4: Where is the waste? The array just mirrors the list. We can do this in O(1) space using three linked list operations: (1) find middle, (2) reverse second half, (3) merge-interleave the two halves.

Implementation

javascript

function reorderList(head) {
  if (!head || !head.next) return;

  // Step 1: Find middle
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // slow is now the middle. Split here.
  let secondHalf = slow.next;
  slow.next = null;  // cut the list

  // Step 2: Reverse second half
  secondHalf = reverseList(secondHalf);

  // Step 3: Merge-interleave
  let first = head, second = secondHalf;
  while (second) {
    const firstNext = first.next;
    const secondNext = second.next;
    first.next = second;
    second.next = firstNext;
    first = firstNext;
    second = secondNext;
  }
}

Full Dry Run: `reorderList(1→2→3→4→5)`

Step 1: Find middle.

code

slow=1, fast=1.
  fast.next=2, fast.next.next=3 → both truthy.
  slow=2, fast=3.
  fast.next=4, fast.next.next=5 → both truthy.
  slow=3, fast=5.
  fast.next=null → stop.
slow=3. secondHalf=slow.next=4→5. slow.next=null.

First half: 1→2→3→null
Second half: 4→5→null

Step 2: Reverse second half.

code

reverseList(4→5→null) → 5→4→null
secondHalf = 5→4→null

Step 3: Merge-interleave.

code

first=1→2→3, second=5→4.

Iteration 1:
  firstNext = first.next = 2→3
  secondNext = second.next = 4
  first.next = second → 1→5
  second.next = firstNext → 5→2→3
  first = 2→3
  second = 4

Iteration 2:
  firstNext = first.next = 3
  secondNext = second.next = null
  first.next = second → 2→4
  second.next = firstNext → 4→3
  first = 3
  second = null

second=null → loop ends.

Final list: 1→5→2→4→3→null ✓

Complexity: O(n) time, O(1) space.

Why fast.next && fast.next.next (not fast && fast.next)?
We want slow to stop at the first middle (for even-length lists). If we used fast && fast.next, slow would stop one position too far. The condition fast.next && fast.next.next stops one iteration earlier.

Problem 4: Palindrome Linked List

Problem: Check if a linked list is a palindrome.
isPalindrome(1→2→2→1) → true
isPalindrome(1→2→3→2→1) → true
isPalindrome(1→2) → false
LeetCode 234.

Four Questions

Q1: What do I have? A singly linked list.
Q2: What do I want? True if the list reads the same forward and backward.
Q3: What is the brute force? Copy to array, two-pointer check. O(n) space.
Q4: Where is the waste? The array. We can reverse just the second half in place, compare with the first half, then restore. O(1) space.

Implementation

javascript

function isPalindrome(head) {
  if (!head || !head.next) return true;

  // Step 1: Find middle
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // For odd length: fast stopped on last node, slow is at true middle.
  // For even length: fast stopped on null, slow is at second of two middles.

  // Step 2: Reverse second half (from slow onward)
  let secondHalf = reverseList(slow);
  let secondCopy = secondHalf;  // save for restoration

  // Step 3: Compare
  let p1 = head, p2 = secondHalf;
  let isPalin = true;
  while (p2) {  // second half is shorter or equal — iterate until p2 exhausted
    if (p1.val !== p2.val) { isPalin = false; break; }
    p1 = p1.next;
    p2 = p2.next;
  }

  // Step 4: Restore (optional but good practice)
  reverseList(secondCopy);

  return isPalin;
}

Dry Run: `isPalindrome(1→2→2→1)`

Step 1: Find middle (using fast && fast.next).

code

slow=1, fast=1.
  fast=1, fast.next=2 → truthy. slow=2, fast=3.
  fast=3, fast.next=1 → truthy. slow=3, fast=null.
  fast=null → stop.
slow = node(2) [second '2', index 2].

Wait — for 1→2→2→1, the nodes are at positions 0,1,2,3. Let me label them: n0(1)→n1(2)→n2(2)→n3(1).

code

slow=n0, fast=n0.
  slow=n1, fast=n2.  (fast=n0.next.next=n2)
  fast=n2, fast.next=n3 → truthy. slow=n2, fast=null. (fast=n2.next.next=n3.next=null)
  fast=null → stop.
slow = n2 (val=2).

Step 2: Reverse from n2 onward.

code

reverseList(n2→n3→null):
  prev=null, curr=n2.
  Step: next=n3. n2.next=null. prev=n2. curr=n3.
  Step: next=null. n3.next=n2. prev=n3. curr=null.
  return n3.
secondHalf = n3(1)→n2(2)→null.

Step 3: Compare.

code

p1=n0(1), p2=n3(1). 1===1 ✓. p1=n1, p2=n2.
p1=n1(2), p2=n2(2). 2===2 ✓. p1=n2, p2=null.
p2=null → loop ends. isPalin=true. ✓

Dry Run: `isPalindrome(1→2→3→2→1)` (odd length)

Nodes: n0(1)→n1(2)→n2(3)→n3(2)→n4(1).

Step 1: Middle.

code

slow=n0, fast=n0.
  slow=n1, fast=n2.
  slow=n2, fast=n4.
  fast=n4, fast.next=null → stop.
slow = n2 (val=3). ← true middle for odd list.

Step 2: Reverse n2→n3→n4.

code

reverseList(n2→n3→n4→null) → n4(1)→n3(2)→n2(3)→null.
secondHalf = n4.

Step 3: Compare.

code

p1=n0(1), p2=n4(1). Match. p1=n1, p2=n3.
p1=n1(2), p2=n3(2). Match. p1=n2, p2=n2.
p1=n2(3), p2=n2(3). Match. p1=n3, p2=null.
p2=null → stop. isPalin=true. ✓

Complexity: O(n) time, O(1) space.

Why iterate while (p2) not while (p1)? The second half is the same length as the first half (for even) or shorter by 1 (for odd — the middle is in the first half). We stop when p2 is exhausted. If we stopped when p1 is exhausted, we'd over-iterate on even-length palindromes.

Problem 5: Copy List With Random Pointer

Problem: Each node has val, next, and random (points to any node or null). Deep copy the list.
LeetCode 138. Hard. Amazon, Meta.

Four Questions

Q1: What do I have? A linked list where each node has an additional random pointer to any node in the list (or null).
Q2: What do I want? A completely independent deep copy — new nodes, same structure.
Q3: What is the brute force? HashMap: old_node → new_node. First pass: create all new nodes, store mapping. Second pass: set next and random pointers using the map. O(n) time, O(n) space.
Q4: Where is the waste (optional — O(1) space solution)? The HashMap. We can interleave cloned nodes into the original list to encode the mapping without extra space.

Approach 1: HashMap (O(n) space, simpler)

javascript

function copyRandomList(head) {
  if (!head) return null;

  const map = new Map();  // old node → new node

  // Pass 1: create all new nodes
  let curr = head;
  while (curr) {
    map.set(curr, new Node(curr.val));
    curr = curr.next;
  }

  // Pass 2: wire up next and random
  curr = head;
  while (curr) {
    if (curr.next) map.get(curr).next = map.get(curr.next);
    if (curr.random) map.get(curr).random = map.get(curr.random);
    curr = curr.next;
  }

  return map.get(head);
}

Dry Run: List = `[7,null]→[13,0]→[11,4]→[10,2]→[1,0]`

(Notation: [val, random_index]. Index 0 = first node, etc.)

code

Nodes: A(7)→B(13)→C(11)→D(10)→E(1)
Random: A→null, B→A, C→E, D→C, E→A

Pass 1: map = {A→A', B→B', C→C', D→D', E→E'}
  (A' through E' are new nodes with correct vals)

Pass 2:
  A: A'.next = B'. A'.random = null (A.random=null).
  B: B'.next = C'. B'.random = A' (B.random=A → map[A]=A').
  C: C'.next = D'. C'.random = E' (C.random=E).
  D: D'.next = E'. D'.random = C' (D.random=C).
  E: E'.next = null. E'.random = A' (E.random=A).

Return A'. ✓

Approach 2: Interleaving (O(1) space)

javascript

function copyRandomListO1(head) {
  if (!head) return null;

  // Pass 1: Interleave — insert each clone right after original
  // Original: A→B→C  becomes  A→A'→B→B'→C→C'
  let curr = head;
  while (curr) {
    const clone = new Node(curr.val);
    clone.next = curr.next;
    curr.next = clone;
    curr = clone.next;
  }

  // Pass 2: Set random pointers
  // curr.next is the clone. curr.random.next is the clone of random target.
  curr = head;
  while (curr) {
    if (curr.random) curr.next.random = curr.random.next;
    curr = curr.next.next;  // skip clone, go to next original
  }

  // Pass 3: Separate the two lists
  const newHead = head.next;
  curr = head;
  while (curr) {
    const clone = curr.next;
    curr.next = clone.next;
    clone.next = clone.next ? clone.next.next : null;
    curr = curr.next;
  }

  return newHead;
}

Why interleaving works: When we insert A' between A and B, we have A→A'→B→B'.... Now curr.random.next is the clone of curr.random — because every original node's clone is exactly one step ahead. This encodes the old-to-new mapping in the list structure itself.

Complexity: O(n) time, O(1) space (ignoring output). Three clean passes.

Problem 6: LRU Cache

Problem: Implement LRU Cache with O(1) get and O(1) put.
LeetCode 146. Hard. Every company. One of the most important design problems.

Fully designed in Chapter 8, Part 9. Here is the complete, clean implementation:

javascript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();

    // Doubly linked list with sentinel head and tail
    this.head = { key: 0, val: 0, prev: null, next: null };  // dummy head (MRU side)
    this.tail = { key: 0, val: 0, prev: null, next: null };  // dummy tail (LRU side)
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _insertFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertFront(node);  // mark as most recently used
    return node.val;
  }

  put(key, val) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = val;
      this._remove(node);
      this._insertFront(node);
    } else {
      const node = { key, val, prev: null, next: null };
      this.map.set(key, node);
      this._insertFront(node);
      if (this.map.size > this.capacity) {
        // Evict LRU (node just before tail)
        const lru = this.tail.prev;
        this._remove(lru);
        this.map.delete(lru.key);
      }
    }
  }
}

Full Dry Run: `LRUCache(2)`

code

Operations: put(1,1), put(2,2), get(1), put(3,3), get(2), put(4,4), get(1), get(3), get(4)

Initial: head ↔ tail. map={}.

put(1,1): Create node(key=1,val=1). Insert front. map={1→n1}.
  List: head ↔ n1(1,1) ↔ tail.

put(2,2): Create n2. Insert front. map={1→n1, 2→n2}.
  List: head ↔ n2(2,2) ↔ n1(1,1) ↔ tail.
  (n2 is MRU, n1 is LRU)

get(1): map has 1. Remove n1, insert front. map unchanged.
  List: head ↔ n1(1,1) ↔ n2(2,2) ↔ tail.
  return 1. ✓  (n1 is now MRU, n2 is LRU)

put(3,3): Create n3. Insert front. map.size=3 > capacity=2.
  Evict tail.prev = n2. Remove n2. map.delete(2). map={1→n1, 3→n3}.
  List: head ↔ n3(3,3) ↔ n1(1,1) ↔ tail.

get(2): map.has(2) → false. return -1. ✓  (2 was evicted)

put(4,4): Create n4. Insert front. map.size=3 > 2.
  Evict tail.prev = n1. Remove n1. map.delete(1). map={3→n3, 4→n4}.
  List: head ↔ n4(4,4) ↔ n3(3,3) ↔ tail.

get(1): map.has(1) → false. return -1. ✓  (1 was evicted)
get(3): map has 3. Move n3 to front. return 3. ✓
  List: head ↔ n3(3,3) ↔ n4(4,4) ↔ tail.
get(4): map has 4. Move n4 to front. return 4. ✓
  List: head ↔ n4(4,4) ↔ n3(3,3) ↔ tail.

Why the node must store its key: When evicting tail.prev, we need to map.delete(key). If the node doesn't store its key, we can't look it up in O(1). This is the subtle design point that many candidates miss.

Complexity: O(1) for both get and put. O(capacity) space.

The real-world version: Node.js's lru-cache npm package (most downloaded, used in Webpack, Babel, ESLint) uses this exact data structure. Redis's maxmemory-policy allkeys-lru uses an approximated version — instead of a true LRU (which requires a doubly linked list per key), it samples a random subset of keys and evicts the oldest among them.

Problem 7: Merge K Sorted Lists

Problem: Merge k sorted linked lists into one sorted linked list.
LeetCode 23. Hard. Google, Amazon, Meta.

Four Questions

Q1: What do I have? Array of k sorted linked lists.
Q2: What do I want? One sorted merged linked list.
Q3: What is the brute force? Collect all values, sort, rebuild. O(N log N) where N = total nodes. Or: repeatedly merge two lists at a time naively — O(kN).
Q4: Where is the waste? Naive merge: merging list 1 with list 2 produces a list of size n1+n2, then merging with list 3 is O(n1+n2+n3), etc. Total: O(kN). With divide and conquer: merge pairs, then pairs of pairs — O(N log k).

Approach: Divide and Conquer (O(N log k))

javascript

function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  return merge(lists, 0, lists.length - 1);
}

function merge(lists, left, right) {
  if (left === right) return lists[left];
  const mid = Math.floor((left + right) / 2);
  const l = merge(lists, left, mid);
  const r = merge(lists, mid + 1, right);
  return mergeTwoLists(l, r);
}

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let curr = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
    else { curr.next = l2; l2 = l2.next; }
    curr = curr.next;
  }
  curr.next = l1 || l2;
  return dummy.next;
}

Why O(N log k): There are log k levels of merging. At each level, every node is touched exactly once across all merges at that level. Total: N × log k.

Alternative: Min Heap (Priority Queue). Push the head of each list into a min-heap. Pop the minimum, add to result, push that node's next. O(N log k) time, O(k) space. Cleaner in languages with built-in heaps. In JavaScript, heaps require manual implementation.

Pattern Recognition Decision Tree

code

New linked list problem:

1. Need to reverse part of the list?
   → Three-pointer iterative reverse. Identify start, end, reconnect edges.

2. "Find middle" subproblem needed?
   → Fast/slow pointer. Remember: `while fast && fast.next` gives first/lower middle.

3. Need to compare front and back?
   → Palindrome pattern: find middle + reverse second half + compare.

4. Two sorted lists to merge?
   → Dummy node + two pointers. One pass, O(n+m).

5. K lists to merge?
   → Divide and conquer (log k levels) or min-heap.

6. Deep copy with cross-references?
   → Two-pass HashMap (simpler) or interleaving (O(1) space).

7. O(1) get/put with recency-based eviction?
   → HashMap + doubly linked list (LRU Cache).

8. Pointer surgery on adjacent nodes?
   → Draw the list before and after. Name every pointer you need. Identify the order that avoids losing references.

5 Practice Problems

1. Trace and Predict

javascript

function f(head) {
  let prev = null, curr = head;
  while (curr) {
    let nextNext = curr.next ? curr.next.next : null;
    if (curr.next) {
      curr.next.next = prev;
      prev = curr.next;
      curr.next = null;
    }
    curr = nextNext;
  }
  return prev;
}

Trace f(1→2→3→4→null). What does this function return? What does it do to the list structure? Is it a complete reversal or something else?

2. Find the Waste

You're given a sorted linked list with duplicates. Remove all duplicates so each element appears only once. 1→1→2→3→3 → 1→2→3.

Write O(n) time, O(1) space. Then: write the harder version — remove all nodes that have duplicates, leaving only distinct values. 1→2→3→3→4→4→5 → 1→2→5. (LeetCode 82 vs 83.) Where does the dummy node become mandatory for version 2?

3. Failure Analysis

javascript

function reverseKGroup(head, k) {
  let curr = head, count = 0;
  while (curr && count < k) { curr = curr.next; count++; }
  if (count < k) return head;  // fewer than k nodes remain
  curr = reverseKGroup(curr, k);  // reverse the rest first
  while (k-- > 0) {              // reverse current k nodes
    const next = head.next;
    head.next = curr;
    curr = head;
    head = next;
  }
  return curr;
}

Trace reverseKGroup(1→2→3→4→5, k=2). Does this produce the correct output 2→1→4→3→5? Trace carefully — this is a real LeetCode 25 solution. Identify: what does curr represent at each stage of the recursion? What does head represent during the while loop?

4. Design Under Constraints

Implement flattenMultilevelDoublyLinkedList (LeetCode 430): a doubly linked list where each node has an optional child pointer to another doubly linked list. Flatten it into a single doubly linked list.

code

1 - 2 - 3 - 4 - 5 - 6
        |
        7 - 8 - 9 - 10
            |
           11 - 12

→ 1-2-3-7-8-11-12-9-10-4-5-6

Use a stack: when you hit a child, push curr.next to stack, follow child. When a list ends and stack is not empty, pop and continue. O(n) time, O(depth) space.

5. Reach Beyond

Design maxTwinSumLinkedList (LeetCode 2130): for a linked list of even length n, the "twin" of node i is node n-1-i. Find the maximum twin sum.

For 5→4→2→1: twins are (5,1) and (4,2). Max twin sum = 6.

The O(1) space solution uses the palindrome technique: find middle, reverse second half, walk both halves simultaneously computing a + b, return max. Implement it, and explain why reversing the second half makes the twin-sum calculation straightforward.

Chapter 8a — Linked List Problem Patterns

Pattern Map

Problem 1: Reverse Linked List

Problem 2: Merge Two Sorted Lists

Problem 3: Reorder List

Four Questions

Implementation

Full Dry Run: reorderList(1→2→3→4→5)

Problem 4: Palindrome Linked List

Four Questions

Implementation

Dry Run: isPalindrome(1→2→2→1)

Dry Run: isPalindrome(1→2→3→2→1) (odd length)

Problem 5: Copy List With Random Pointer

Four Questions

Approach 1: HashMap (O(n) space, simpler)

Dry Run: List = [7,null]→[13,0]→[11,4]→[10,2]→[1,0]

Approach 2: Interleaving (O(1) space)

Problem 6: LRU Cache

Full Dry Run: LRUCache(2)

Problem 7: Merge K Sorted Lists

Four Questions

Approach: Divide and Conquer (O(N log k))

Pattern Recognition Decision Tree

5 Practice Problems

Full Dry Run: `reorderList(1→2→3→4→5)`

Dry Run: `isPalindrome(1→2→2→1)`

Dry Run: `isPalindrome(1→2→3→2→1)` (odd length)

Dry Run: List = `[7,null]→[13,0]→[11,4]→[10,2]→[1,0]`

Full Dry Run: `LRUCache(2)`