Pattern Reference
Linked List
"Reverse, merge, detect cycles, find middle, LRU cache."
Loading...
Deep Dive Tutorial
lightbulb
While loop condition rule: Look at what you access INSIDE the loop.
- Access
- Access
This prevents null pointer errors without special-casing every edge condition.
- Access
curr.next → condition: while (curr)- Access
curr.next.next → condition: while (curr && curr.next)This prevents null pointer errors without special-casing every edge condition.
key
Dummy node: Whenever the head node might be modified or removed, create a dummy node that points to head. This turns "delete head" into a normal node deletion — no special cases. Return
dummy.next at the end.Core Templates
In-place reversal (prev always starts null)
// prev = null because the last node of reversed list points to nothing
let prev = null, curr = head;
while (curr) {
const next = curr.next; // save next before overwriting
curr.next = prev; // reverse the pointer
prev = curr; // prev advances to current
curr = next; // curr advances to saved next
}
return prev; // prev is the new headSlow/fast pointer — find middle
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// slow = middle node
// for even-length: slow = second of the two middlesPartition into two lists, merge at end
let left = new ListNode(), right = new ListNode();
const lHead = left, rHead = right;
let curr = head;
while (curr) {
if (condition(curr.val)) { left.next = curr; left = left.next; }
else { right.next = curr; right = right.next; }
curr = curr.next;
}
right.next = null; // CRITICAL: null-terminate right to prevent cycle
left.next = rHead.next;
return lHead.next;Worked Problems
More Worked Problems
lightbulb
Recursive linked list reversal: works by reversing the rest of the list first, then fixing the current node's pointers when recursion unwinds.
``
Linked list pattern checklist:
- "Find middle" → slow/fast pointers (slow ends at middle)
- "Detect cycle" → Floyd's: slow+fast, if they meet, cycle exists
- "k-th from end" → two pointers gap k apart
- "Merge/sort" → divide and conquer (merge sort on lists)
- "Copy with extra pointers" → HashMap OR interleave trick (O(1) space)
``
if (!head || !head.next) return head;
const newHead = reverse(head.next);
head.next.next = head; // last node of reversed part now points back
head.next = null; // break old forward link
return newHead;
Linked list pattern checklist:
- "Find middle" → slow/fast pointers (slow ends at middle)
- "Detect cycle" → Floyd's: slow+fast, if they meet, cycle exists
- "k-th from end" → two pointers gap k apart
- "Merge/sort" → divide and conquer (merge sort on lists)
- "Copy with extra pointers" → HashMap OR interleave trick (O(1) space)