Linked Lists: Deriving the Optimal Solution for 5 Problems (LC 206/21/141/143/146)

Linked list problems rarely test "algorithmic difficulty" — they test careful pointer work: one wrong next and you break the chain or loop forever. Drill these core moves into muscle memory and this family is solid:

• The three-pointer reversal (the prev / curr / next dance)
• The dummy head (kills the "attach at the head" edge case)
• Fast/slow pointers (cycles, midpoints)
• HashMap + doubly linked list (O(1) design problems like LRU)

Continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• Reverse (206) → merge (21) → cycle via fast/slow (141) → reorder (143, all three combined) → LRU Cache (146, a design problem)

🔗 Node definition: Python node.val / node.next; C++ ListNode { int val; ListNode *next; }.

① LC 206 — Reverse Linked List

📋 Problem: Reverse a singly linked list and return the new head.

Example: 1→2→3→4→5 → 5→4→3→2→1

🧭 From reading the problem to the solution

1. Break it down: point each node's next backward. The catch: save the original next before reversing, or the chain breaks.
2. Key insight (three pointers): keep prev (head of the reversed part), curr (current), nxt (temp). Each step: save nxt = curr.next, point curr.next to prev, then advance all.
3. Optimum: iterative, O(1) space.

def reverseList(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next        # save next before breaking the link
        curr.next = prev       # reverse the pointer
        prev = curr            # advance both
        curr = nxt
    return prev                # prev is the new head

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nxt = curr->next;   // save next
        curr->next = prev;            // reverse
        prev = curr;                  // advance
        curr = nxt;
    }
    return prev;
}

• Complexity: O(n) time, O(1) space.
• Pitfall: ① save nxt before changing curr.next — reverse the order and you break the chain; ② return prev, not curr (curr is null at the end); ③ the recursive version is elegant but uses O(n) stack.

② LC 21 — Merge Two Sorted Lists

📋 Problem: Merge two sorted linked lists into one sorted list and return it.

Example: l1 = 1→2→4, l2 = 1→3→4 → 1→1→2→3→4→4

🧭 From reading the problem to the solution

1. Break it down: both are sorted; compare the two heads, attach the smaller — a two-pointer merge.
2. Bottleneck: attaching to the result tail has no predecessor for the first node, needing if-handling for the head.
3. Key insight (dummy head): build a virtual head dummy; attach everything after it and return dummy.next — eliminating the "first node" edge case entirely.
4. Optimum: dummy + tail pointer.

def mergeTwoLists(l1, l2):
    dummy = tail = ListNode(0)        # virtual head kills the edge case
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1; l1 = l1.next
        else:
            tail.next = l2; l2 = l2.next
        tail = tail.next
    tail.next = l1 or l2              # attach the remaining tail
    return dummy.next

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; }
        else                    { tail->next = l2; l2 = l2->next; }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;        // attach the rest
    return dummy.next;
}

• Complexity: O(m + n) time, O(1) space.
• Pitfall: ① the dummy head is the universal simplifier for linked lists — use it whenever the result's head might change; ② attach the entire remaining tail (l1 or l2) after the loop; ③ use <= for stability.

③ LC 141 — Linked List Cycle

📋 Problem: Determine whether a linked list has a cycle (some node's next points back to an earlier node).

Example: 3→2→0→-4 with -4 pointing back to 2 → true; no cycle → false

🧭 From reading the problem to the solution

1. Break it down: with a cycle, walking from the head never reaches null.
2. Brute force: a HashSet of visited nodes; a repeat means a cycle, O(n) time and space.
3. Key insight (fast/slow, Floyd's): slow moves 1 step, fast moves 2. With a cycle, fast eventually laps and meets slow (relative speed 1, they must meet); without one, fast reaches null first. Space drops to O(1).
4. Optimum: tortoise and hare.

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # 1 step
        fast = fast.next.next       # 2 steps
        if slow == fast:            # they meet → cycle
            return True
    return False                    # fast hit null → no cycle

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

• Complexity: O(n) time, O(1) space.
• Pitfall: ① loop condition fast and fast.next (fast takes two steps, both must exist); ② compare nodes (addresses), not values; ③ for LC 142 (find the cycle's start): after meeting, move one pointer to the head and advance both at the same speed — they meet at the entrance.

④ LC 143 — Reorder List

📋 Problem: Reorder L0→L1→…→Ln into L0→Ln→L1→Ln-1→L2→…, modifying pointers only (not values).

Example: 1→2→3→4 → 1→4→2→3; 1→2→3→4→5 → 1→5→2→4→3

🧭 From reading the problem to the solution

1. Break it down: observe the result — it's the first half interleaved with the reversed second half.
2. Key insight (combine three moves): decompose into three problems you already know:
   • ① Find the midpoint (fast/slow) → split into two halves.
   • ② Reverse the second half (206's three pointers).
   • ③ Merge the two halves alternately.
3. Optimum: O(n) time, O(1) space, no extra array.

def reorderList(head):
    # 1. find middle (slow ends at the middle)
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 2. reverse the second half
    second = slow.next
    slow.next = None                 # cut into two halves
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    # 3. merge the two halves alternately
    first, second = head, prev
    while second:
        f_nxt, s_nxt = first.next, second.next
        first.next = second
        second.next = f_nxt
        first, second = f_nxt, s_nxt

void reorderList(ListNode* head) {
    // 1. find middle
    ListNode* slow = head; ListNode* fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    // 2. reverse second half
    ListNode* second = slow->next;
    slow->next = nullptr;
    ListNode* prev = nullptr;
    while (second) {
        ListNode* nxt = second->next;
        second->next = prev; prev = second; second = nxt;
    }
    // 3. merge alternately
    ListNode* first = head; second = prev;
    while (second) {
        ListNode* fn = first->next; ListNode* sn = second->next;
        first->next = second; second->next = fn;
        first = fn; second = sn;
    }
}

• Complexity: O(n) time, O(1) space.
• Pitfall: ① the value is in "decompose into three known sub-problems" — say that in the interview and you've half-won; ② cut the halves with slow.next = None; ③ when merging, save both nexts before rewiring or you break the chain.

⑤ LC 146 — LRU Cache

📋 Problem: Design an LRU (Least Recently Used) cache with get(key) and put(key, value), both in O(1). When full, evict the least recently used item.

Example: capacity = 2; put(1,1) put(2,2) get(1)→1 put(3,3) (evicts 2) get(2)→-1

🧭 From reading the problem to the solution

1. Break it down: need O(1) "lookup value" + O(1) "update use-order" + O(1) "evict oldest."
2. Bottleneck: a HashMap alone gives O(1) lookup but doesn't track order; an array/list alone tracks order but lookup or moving is O(n).
3. Key insight (HashMap + doubly linked list):
   • HashMap: key → node, O(1) location.
   • Doubly linked list: tracks order (head = most recent, tail = least recent). Doubly is needed to splice any node out / to the front in O(1).
   • get: found → move to head. put: add to head; over capacity → remove tail.
4. Optimum: combine them, all ops O(1).

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()        # ordered = built-in HashMap + DLL
        self.cap = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)       # mark as most recently used
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)   # evict least recently used

class LRUCache {
    int cap;
    list<pair<int,int>> dll;                       // front = most recent
    unordered_map<int, list<pair<int,int>>::iterator> pos;
public:
    LRUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (pos.find(key) == pos.end()) return -1;
        dll.splice(dll.begin(), dll, pos[key]);    // O(1) move to front
        return pos[key]->second;
    }
    void put(int key, int value) {
        if (pos.count(key)) {
            pos[key]->second = value;
            dll.splice(dll.begin(), dll, pos[key]);
            return;
        }
        if ((int)dll.size() == cap) {
            pos.erase(dll.back().first);            // evict LRU (tail)
            dll.pop_back();
        }
        dll.push_front({key, value});
        pos[key] = dll.begin();
    }
};

• Complexity: get / put both O(1), O(capacity) space.
• Pitfall: ① the core is "HashMap to locate + doubly linked list to order" — interviews often want you to hand-roll the doubly linked list (don't just lean on OrderedDict; be able to explain the internals); ② doubly linked is needed to splice out a node in O(1) (singly can't reach the predecessor); ③ C++ list::splice is the O(1) node-move tool.

One Table to Remember It All

Pattern-Recognition Cheats

• "reverse / partial reverse" → three pointers prev/curr/nxt (save before rewiring).
• "merge / head might change" → a dummy virtual head.
• "has a cycle / find the midpoint / kth from the end" → fast/slow pointers.
• "reorder / palindrome list" → find midpoint + reverse the second half + merge (decompose).
• "O(1) get/put with eviction" → HashMap + doubly linked list.

The essence of linked list problems isn't the algorithm — it's pointer discipline: save first, rewire next, advance last; use a dummy when the head can change; pair a doubly linked list when you need order. Drill these moves into reflex and your chains stop breaking.