Linked List

Linked lists are where "just use recursion, it's cleaner" stops being free advice. Almost every problem in this topic has a genuinely elegant recursive solution and a slightly less pretty iterative one — and the iterative one is usually the right answer, because a linked list's length isn't bounded the way a typical function's call stack is. This topic is as much about that judgment call as it is about the pointer manipulation itself.

Two runner techniques carry most of this topic

• Fast/slow pointers ("the runner technique"). One pointer moves one step at a time, another moves two. This single idea gives you: the middle of a list in one pass (Middle of the Linked List), whether a cycle exists at all (Linked List Cycle), and — with one extra step — exactly where that cycle begins (Linked List Cycle II). All three are the same runner, applied to a slightly different question.
• The gap technique. Advance one pointer n steps ahead of a second pointer, then move both together until the lead pointer runs out. Remove Nth Node From End of List is the clean version of this — it turns "I don't know the list's length" into a single pass instead of two.

Recursion depth is a real cost that Big-O hides

Reverse Linked List has a famously elegant three-line recursive solution. It's also, in the most literal sense, a ticking time bomb: it recurses once per node, so a list with hundreds of thousands of nodes recurses hundreds of thousands of levels deep — and blows the call stack. Big-O notation says both the recursive and iterative versions are O(n) time — it says nothing about the fact that one of them can crash a real process on a long enough input while the other never can. This is exactly the kind of thing "efficient code" means beyond just the complexity class: the iterative three-pointer walk (prev, curr, next) does the identical work with zero growing stack.

// Elegant, and a real production risk on a long enough list --
// recurses once per node, so stack depth grows with n.
ListNode* reverse_recursive(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode* new_head = reverse_recursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return new_head;
}

// Same O(n) time, same result -- but O(1) stack depth, always.
ListNode* reverse_iterative(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

Reverse Nodes in k-Group has the same trap in a sneakier form: the "obvious" recursive solution recurses once per group, not once per node — which sounds safe, but for a small k on a long list, n / k is still large enough to overflow the stack. The fix is the same: do it iteratively, one flat loop over the whole list.

Common mistakes

• Not using a dummy head node when the operation might need to change the head itself (Remove Nth Node From End, Merge k Sorted Lists) — without one, removing or replacing the actual first node becomes a separate special case instead of just falling out of the general logic.
• Forgetting to restore state you mutated for a check (Palindrome Linked List reverses the second half to compare it — and needs to reverse it back before returning, or the list comes back corrupted even though the answer was correct).
• Losing the "next" pointer before rewiring it — the single most common linked-list bug: writing curr->next = prev before saving the original curr->next in a temporary, which severs your only path to the rest of the list.
• Confusing "same value" with "same node" in Copy List with Random Pointer — the whole point is that the copy's pointers must reference the *new* nodes, not accidentally alias the original list; a broken "copy" that just returns the same nodes will pass value checks but isn't a copy at all.