LC Patterns — Linked Lists

struct ListNode { int val; ListNode* next; ListNode(int x): val(x), next(nullptr) {} };

// Standard walk with previous — powers deletion, reversal, insertion:
ListNode* prev = dummy; ListNode* cur = head;
while (cur) { /* ... */ }

// The reversal triple — THE core move; drill until automatic:
ListNode* nxt = cur->next;    // 1. save
cur->next = prev;             // 2. rewire
prev = cur; cur = nxt;        // 3. advance

// Fast & slow:
ListNode* slow = head; ListNode* fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }

Facts to have loaded

while (fast && fast->next) is the universal safe guard for two-stepping — works for odd and even lengths. Deletion needs the node before — hence prev-pointers and dummies. In C++ think about ownership: delete removed nodes (no GC). Doubly linked lists (design): every splice touches 4 pointers; sentinel head and tail remove all edge cases — if you write a->next = b without b->prev = a in the same breath, the structure is already corrupt.

What it is: Reverse the whole list, a sublist [left, right], or every k-node group — by walking forward while pointing each node backward. The single most important mechanical skill in this file; the harder problems just aim it at a window.

Intuition: you can't walk a singly linked list backward — but you can make the arrows point backward as you pass, carrying a prev that grows into the reversed prefix. Sublist reversal (92) = walk to the node before left, reverse right−left+1 steps, then stitch both seams. K-group (25) = sublist reversal in a loop with a length probe (only reverse complete groups); 24 (swap pairs) is the k = 2 special case.

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur) {
        ListNode* nxt = cur->next;    // 1. save
        cur->next = prev;             // 2. rewire
        prev = cur; cur = nxt;        // 3. advance
    }
    return prev;                      // new head
}

What it is: Two pointers, one twice as fast. When fast finishes, slow is at the middle; if there's a cycle they must meet inside it; and a second phase finds the exact node where the cycle begins.

Intuition: in a cycle, fast gains exactly 1 node on slow each step, so the gap shrinks to 0 — they meet; no cycle ⇒ fast hits null. Cycle entry (142): with head-to-entry a, meeting point b into a cycle of length c, at meeting slow walked a+b, fast 2(a+b)=a+b+kc ⇒ a = kc − b — so a pointer from the head and the meeting-point pointer, both at speed 1, meet exactly at the entry. Rehearse this — it's the thing 142 tests.

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head; ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next; fast = fast->next->next;
        if (slow == fast) {                      // phase 1: they meet
            ListNode* p = head;
            while (p != slow) { p = p->next; slow = slow->next; }   // phase 2: walk to entry
            return p;
        }
    }
    return nullptr;                              // no cycle
}

What it is: Two pointers moving at the same speed but separated by a fixed gap, or synchronized across two lists — so when one hits a landmark, the other is exactly where you need to act. One pass, no length precomputation.

Intuition: n-th from the end (19): give the lead pointer an n-node head start; when it reaches the end, the trailer is n from the end — an invariant carried to the finish. Intersection (160): two lists sharing a tail — walk A through list1 then list2, B through list2 then list1; both walk m+n and arrive at the intersection together (or reach null together if disjoint). Rotate (61): close into a ring, walk n − k%n, cut.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0); dummy.next = head;
    ListNode* lead = &dummy; ListNode* trail = &dummy;
    for (int i = 0; i <= n; ++i) lead = lead->next;   // n+1 ahead from dummy
    while (lead) { lead = lead->next; trail = trail->next; }
    trail->next = trail->next->next;                  // trailer stops BEFORE the victim
    return dummy.next;
}

What it is: Break a list into sublists by a rule (less-than-x vs the rest; odd vs even positions), or weave sorted lists into one — building output lists tail-first with dummy heads. The stable-splice discipline: nodes keep their relative order because you only ever append.

Intuition: merge two sorted (21): a zipper with a dummy head + tail pointer, and when one list empties, append the remainder in one move. Partition (86): don't shuffle nodes in place — run two collector lists (< x and ≥ x) with their own dummies, then join; stability is automatic because appending preserves order. Odd-even (328): the same two-collector idea keyed by position parity, done in place by leapfrogging.

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
    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;          // append the whole remainder
    return dummy.next;
}

What it is: Sort a linked list in O(n log n). Arrays reach for quicksort/heapsort; lists can't (no random access) — but merge sort actually gets nicer on lists: split via fast/slow, merge via Pattern 4's zipper, no auxiliary array.

Intuition: merge sort's two primitives — split in half, merge two sorted — are exactly Patterns 2 and 4, both O(1)-extra on lists. So 148 is a composition test: find the middle (first middle, then cut), recurse, zip. The true-O(1)-space follow-up is bottom-up merge sort (merge runs of width 1, 2, 4, … iteratively). Merge k lists (23): pairwise divide-and-conquer, O(N log k).

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;             // base case doubles as guard
    ListNode* slow = head; ListNode* fast = head->next; // fast = head->next → left gets the shorter half
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* mid = slow->next; slow->next = nullptr;   // SEVER the halves
    return mergeTwoLists(sortList(head), sortList(mid));
}

What it is: Remove nodes matching a condition — by value, duplicated-in-sorted, or any predicate. All powered by one loop shape: prev anchored on the last surviving node, cur scouting ahead, and the dummy making "before the head" a real place.

Intuition: deletion = making the predecessor skip the victim — so the loop's real subject is prev, not cur. Remove all matching values (203): if cur matches, skip and prev stays (the next node needs vetting too); else advance prev. Dedupe-all-copies (82): prev advances only when exactly one copy passed. Contrast 83 (keep one copy — no dummy, no prev). The 82-vs-83 distinction — survivor-anchored vs current-anchored — is the interview.

ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(0); dummy.next = head;
    ListNode* prev = &dummy;
    while (prev->next) {
        if (prev->next->val == val) prev->next = prev->next->next; // skip; prev STAYS
        else prev = prev->next;                                   // advance only when kept
    }
    return dummy.next;
}

What it is: The three-step composite that solves "compare/combine the two halves" problems in O(n) time, O(1) space: find the middle (Pattern 2), reverse the second half (Pattern 1), then walk/weave the two halves (Pattern 3/4). The single most-asked linked-list composition.

Intuition: questions that pair position i with n−1−i (palindrome, reorder L0→Ln→L1→Ln−1…, twin sums) need to read the list from both ends — impossible singly-linked, unless you reverse the back half. The array alternative (copy out, two indices) is O(n) space; the combo is the O(1)-space answer the problem is fishing for — offer the array version as the baseline, then deliver the combo.

bool isPalindrome(ListNode* head) {
    // 1. first middle + cut
    ListNode* slow = head; ListNode* fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* second = slow->next; slow->next = nullptr;
    // 2. reverse the second half
    ListNode* prev = nullptr;
    while (second) { ListNode* n = second->next; second->next = prev; prev = second; second = n; }
    // 3. walk both halves
    for (ListNode* p = head, *q = prev; q; p = p->next, q = q->next)
        if (p->val != q->val) return false;
    return true;
}

What it is: Numbers stored as linked lists of digits — add them, with digits in forward or reverse order. The carry loop, re-hosted on list nodes.

Intuition: addition wants the least-significant digit first. LC 2 hands you exactly that (lists reversed) — one pass, dummy-headed output, a carry variable, loop while l1 || l2 || carry (the carry can outlive the digits). LC 445 stores most-significant first → either reverse both inputs (then it's LC 2) or use two stacks (no mutation, build by prepending). 1290 (binary→int) is the forward warm-up: Horner's rule num = num*2 + bit.

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); ListNode* tail = &dummy; int carry = 0;
    while (l1 || l2 || carry) {
        int s = carry;
        if (l1) { s += l1->val; l1 = l1->next; }
        if (l2) { s += l2->val; l2 = l2->next; }
        carry = s / 10;
        tail->next = new ListNode(s % 10);
        tail = tail->next;
    }
    return dummy.next;
}

What it is: Lists with extra pointers per node (random, child, prev) that must be deep-copied, flattened, or spliced — where the difficulty is keeping a correspondence between old and new structure without losing threads.

Intuition: copy-with-random (138): the randoms point at original nodes; the copy needs them pointing at copied nodes → an old→new map. Hashmap version: two passes, O(n) space, correct. The O(1)-space set-piece interleaves copies into the original (A→A'→B→B'…) so each copy's random is orig->random->next, then unzips — and the unzip must fully restore the original. Flatten multilevel (430): DFS splicing child chains in with a stack of pending nexts.

Node* copyRandomList(Node* head) {
    unordered_map<Node*, Node*> map;
    for (Node* cur = head; cur; cur = cur->next)     // pass 1: create copies
        map[cur] = new Node(cur->val);
    for (Node* cur = head; cur; cur = cur->next) {   // pass 2: wire through the map
        map[cur]->next   = map[cur->next];           // map[nullptr] default-inserts nullptr
        map[cur]->random = map[cur->random];
    }
    return map[head];
}

What it is: Design problems where a linked list is chosen by you — because it's the only container with O(1) removal from the middle given a node reference. LRU cache is the canonical interview: a hashmap for O(1) lookup + a doubly linked list for O(1) recency reordering.

Intuition: LRU needs three O(1) ops: find an entry (hashmap → node), move to "most recent" (unlink + relink at one end — this is why it must be a linked list; an array shifts in O(n)), evict the least recent (remove at the other end). The composition — hashmap points at list nodes; list order encodes recency — is the single most important data-structure composition in interviews, and generalizes: LFU (460) = hashmap + a DLL per frequency bucket.

class LRUCache {
    struct Node { int key, val; Node *prev, *next;
                  Node(int k, int v): key(k), val(v), prev(nullptr), next(nullptr) {} };
    int cap;
    unordered_map<int, Node*> map;
    Node *head, *tail;                              // sentinels; head side = most recent
    void remove(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
    void addFront(Node* n) { n->next = head->next; n->prev = head;
                             head->next->prev = n; head->next = n; }
public:
    LRUCache(int capacity): cap(capacity) {
        head = new Node(0,0); tail = new Node(0,0);
        head->next = tail; tail->prev = head;
    }
    int get(int key) {
        if (!map.count(key)) return -1;
        Node* n = map[key]; remove(n); addFront(n);          // promote
        return n->val;
    }
    void put(int key, int value) {
        if (map.count(key)) { Node* n = map[key]; n->val = value; remove(n); addFront(n); return; }
        if ((int)map.size() == cap) {                        // evict LRU at the tail
            Node* lru = tail->prev; remove(lru); map.erase(lru->key); delete lru;
        }
        Node* n = new Node(key, value); map[key] = n; addFront(n);
    }
};