🔗 Linked List

A learning sheet — there are barely any "algorithms" here. It's pointer hygiene: a sentinel head, and never overwrite a pointer before you've saved what it pointed to.

🧠 1 · How to think (and invent it)

A node is just { val, next }. You can't index it; you can only walk forward and rewire .next. Almost every bug is one of two things: you lost a reference (overwrote a pointer before saving what came next), or you special-cased the head and got it wrong.

Watch it get invented — Reverse a List

Reverse 1 → 2 → 3 in place, O(1) space. The naive cur.next = prev looks right… and instantly orphans the rest of the list.

1. The trap. If you flip cur.next to point backward before remembering cur.next, you can never reach node 2 or 3 again.
2. The fix. Carry three pointers: prev (already-reversed part), cur (node being flipped), and a saved next (the untouched rest). Each step: save next → flip → advance both.
3. Payoff. One pass, no extra memory; prev ends as the new head.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The four core patterns

Node shape throughout: class ListNode { val: number; next: ListNode | null }. Each pattern: a one-liner, a 🔑 invariant, a template, and a 🎤 interview lens.

4.1 · Reversal — the prev / cur / next dance

“Save next, flip the arrow back, slide both pointers forward.”

function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null, cur = head;
  while (cur) {
    const next = cur.next;   // SAVE before rewiring
    cur.next = prev;         // flip the arrow backward
    prev = cur; cur = next;  // advance the window
  }
  return prev;               // new head
}

4.2 · Fast & slow runners

“Two speeds turn ‘where's the middle / is there a loop?’ into one pass.”

Setup: slow += 1, fast += 2. This is the linked-list face of the fast & slow two-pointer — the proofs live there; here are the four staples.

// Middle node (for even length, returns the second middle)
function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; }
  return slow;
}

// Palindrome list: find middle → reverse 2nd half → compare
function isPalindrome(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow!.next; fast = fast.next.next; }
  let prev: ListNode | null = null;            // reverse from slow
  while (slow) { const n = slow.next; slow.next = prev; prev = slow; slow = n; }
  let a = head, b = prev;                       // compare halves
  while (b) { if (a!.val !== b.val) return false; a = a!.next; b = b.next; }
  return true;
}

4.3 · Dummy head & splicing

“Put a fake node in front so the head is never a special case.”

Setup: create dummy with dummy.next = head, keep a moving tail/prev, and return dummy.next. Deletions and merges that would touch the head now Just Work.

// Merge two sorted lists
function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode(0); let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else                { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;            // attach the remaining run
  return dummy.next;
}

// Remove n-th node from the end — one pass, dummy avoids the head edge-case
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head); let fast = dummy, slow = dummy;
  for (let i = 0; i < n; i++) fast = fast.next!;   // open a gap of n
  while (fast.next) { fast = fast.next; slow = slow.next!; }
  slow.next = slow.next!.next;                      // slow sits just before the target
  return dummy.next;
}

4.4 · Compose the primitives

“Hard list problems = find-middle + reverse + merge, glued together.”

Setup: the toughest problems decompose into the primitives above. The discipline that makes them work: null-terminate between stages so you don't accidentally weld a cycle.

// Reorder List:  1→2→3→4→5  becomes  1→5→2→4→3
function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;
  let slow = head, fast = head;                            // 1) middle
  while (fast.next && fast.next.next) { slow = slow.next!; fast = fast.next.next; }
  let second: ListNode | null = slow.next; slow.next = null;   // cut!
  let prev: ListNode | null = null;                        // 2) reverse 2nd half
  while (second) { const n = second.next; second.next = prev; prev = second; second = n; }
  let first: ListNode | null = head; second = prev;        // 3) interleave
  while (second) {
    const f = first!.next, s = second.next;
    first!.next = second; second.next = f;
    first = f; second = s;
  }
}

// Swap nodes in pairs — dummy + careful rewire
function swapPairs(head: ListNode | null): ListNode | null {
  const dummy = new ListNode(0, head); let prev = dummy;
  while (prev.next && prev.next.next) {
    const a = prev.next, b = a.next!;
    a.next = b.next; b.next = a; prev.next = b;   // prev → b → a → …
    prev = a;
  }
  return dummy.next;
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 86 Partition List — two lists behind two dummy heads, then stitch
function partition(head: ListNode | null, x: number): ListNode | null {
  const lessHead = new ListNode(0), geHead = new ListNode(0);
  let l = lessHead, g = geHead;
  for (let n = head; n; n = n.next) {
    if (n.val < x) { l.next = n; l = n; }
    else           { g.next = n; g = n; }
  }
  g.next = null;                 // the last ≥x node may still point into the <x part → cycle if left
  l.next = geHead.next;
  return lessHead.next;
}

// 708 Insert into a Sorted Circular Linked List
function insertCircular(head: ListNode | null, x: number): ListNode {
  if (!head) { const n = new ListNode(x); n.next = n; return n; }
  let prev = head, cur = head.next!;
  do {
    if (prev.val <= x && x <= cur.val) break;                          // normal slot
    if (prev.val > cur.val && (x >= prev.val || x <= cur.val)) break;  // wrap point: max → min
    prev = cur; cur = cur.next!;
  } while (prev !== head);                                              // one full lap (all-equal list falls through)
  prev.next = new ListNode(x, cur);
  return head;
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• reverse reverseList (and the recursive form)
• fast/slow middleNode + isPalindrome
• dummy mergeTwoLists + removeNthFromEnd
• compose reorderList + swapPairs

For each: draw the before/after arrows and mark where you save a pointer, then write the code.