Interview Pattern Catalog

Tell: "you may need to modify the head", "remove all nodes equal to…", any deletion where the first node might go.

A sentinel node in front of the list means the real head is never a special case — prev always exists.

ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
while (prev->next) {
    if (shouldRemove(prev->next))
        prev->next = prev->next->next;   // unlink; prev stays put
    else
        prev = prev->next;
}
return dummy.next;

Solves: 203 Remove Elements, 82 Remove Duplicates II, 19 Remove n-th From End, 2 Add Two Numbers.

Trap: returning head instead of dummy.next (the head may have been deleted), and advancing prev even on the iteration where you unlinked.

Tell: in-place deletion, "delete the node" — especially when even the head can be removed with no special case.

Hold the address of the pointer that points at the current node. Unlinking becomes a single write and the head needs no special handling.

ListNode** pp = &head;               // pp aims at the pointer to cur
while (*pp) {
    if (shouldRemove(*pp)) {
        ListNode* dead = *pp;
        *pp = (*pp)->next;           // splice out, head included
        delete dead;
    } else {
        pp = &(*pp)->next;          // advance ONLY when keeping
    }
}
return head;

Solves: 203 Remove Elements, 83 Remove Duplicates, 237 Delete Node (the copy-forward variant).

Trap: advancing pp in both branches — after a delete, *pp already points at the next node, so advancing skips it.

Tell: "the middle", "is there a cycle", "without knowing the length", "in one pass".

Two pointers moving at different rates. When the fast one falls off the end, the slow one is at a structurally meaningful place.

ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
    slow = slow->next;            // 1 step
    fast = fast->next->next;      // 2 steps
}
// slow == middle (the second middle when the length is even)

Solves: 876 Middle of the List, 141 Cycle, 142 Cycle II, 234 Palindrome.

Trap: the loop condition decides which middle you land on. while (fast && fast->next) gives the second middle; starting fast = head->next gives the first. Pick deliberately.

Tell: "n-th node from the end", "where two lists intersect", a fixed offset between two cursors.

Open a gap of exactly n between two pointers, then move both until the leader hits the end. The trailer is now n from the end.

ListNode dummy(0);
dummy.next = head;
ListNode* lead = &dummy;
for (int i = 0; i < n; ++i) lead = lead->next;   // gap of n
ListNode* trail = &dummy;
while (lead->next) { lead = lead->next; trail = trail->next; }
// trail->next is the n-th node from the end (safe to delete)

Solves: 19 Remove n-th From End, 160 Intersection, 1721 Swapping Nodes.

Trap: off-by-one in the gap. Anchoring both pointers on a dummy makes removing the head fall out for free instead of needing its own branch.

Tell: "reverse", "palindrome", "reorder", "in groups of k", "O(1) extra space".

The three-pointer save–rewire–advance loop. Every reordering problem is this loop applied to a chosen span.

ListNode* prev = nullptr;
ListNode* cur  = head;
while (cur) {
    ListNode* nx = cur->next;   // save
    cur->next = prev;           // rewire
    prev = cur;                 // advance
    cur = nx;
}
return prev;   // new head of the reversed span

Solves: 206 Reverse, 92 Reverse II, 25 K-Group, 143 Reorder.

Trap: for a sub-list you must remember the node before the segment and the segment's original head (its future tail) to reconnect — see Sublist & K-Group Reversal.

Tell: "partition around x", "group odd and even positions", "separate by a predicate".

Walk once, appending each node to one of two sublists by a test, then join them. Two dummies keep the append O(1).

ListNode lo(0), hi(0);
ListNode* lt = &lo;
ListNode* ht = &hi;
for (ListNode* p = head; p; p = p->next) {
    if (pred(p)) { lt->next = p; lt = p; }
    else         { ht->next = p; ht = p; }
}
ht->next = nullptr;      // TERMINATE, or you build a cycle
lt->next = hi.next;
return lo.next;

Solves: 86 Partition, 328 Odd Even, 725 Split in Parts.

Trap: forgetting ht->next = nullptr. The last appended node keeps its old next and closes a loop — the accidental cycle from Pitfalls.

Tell: "sorted", "merge two/k sorted lists", "sort a list".

The two-way merge with a dummy tail is the primitive; k-way and merge sort are it applied recursively.

ListNode dummy(0);
ListNode* 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 ? a : b;   // one list is empty; attach the remainder
return dummy.next;

Solves: 21 Merge Two, 23 Merge k, 148 Sort List, 147 Insertion Sort.

Trap: merging k lists by folding them in one at a time is O(kN). Use a heap (O(N log k)) or pairwise divide and conquer instead — see Merging.

Tell: "O(1) get and put", "least recently used", "clone with random pointers".

A hash map for O(1) lookup, a doubly linked list for O(1) reordering/eviction. The map stores iterators/node pointers into the list.

// LRU: unordered_map<int, list<pair<int,int>>::iterator> pos; list<pair<int,int>> items;
void put(int key, int val) {
    if (pos.count(key)) items.erase(pos[key]);   // drop the stale node
    items.push_front({key, val});                 // most-recent at front
    pos[key] = items.begin();
    if (items.size() > cap) {                     // evict the tail
        pos.erase(items.back().first);
        items.pop_back();
    }
}

Solves: 146 LRU Cache, 460 LFU Cache, 138 Copy with Random Pointer, 355 Design Twitter.

Trap: forgetting to erase the stale map entry on eviction (a slow leak of keys), or reaching for a singly linked list — you cannot unlink a node from it in O(1).