Traversals & Access Patterns

Two-pointer (slow/fast) — two references advance at different speeds or with a fixed offset in a single pass:

• Cycle detection: slow moves 1 step, fast moves 2; they meet inside any cycle (Floyd's algorithm).
• Middle finding: when fast hits tail, slow is at the middle. For even-length lists, slow lands at the first of the two middles; initialise fast = head.next to land at the second middle.
• Nth from end: advance fast N steps first, then move both together; when fast hits null, slow is at the target.
• Intersection: when one pointer reaches null, redirect it to the other list's head; they meet at the intersection or both reach null simultaneously. Recursive traversal — models the list as head + tail sublist. Natural for problems that process nodes in reverse order (e.g., reverse, add two numbers). Risk: O(n) stack depth; Python's default recursion limit is 1000.

---

Topic-Specific Operations

Delete a given node (singly, no predecessor reference) — copy successor's value into current node, then skip successor:

node.val = node.next.val; node.next = node.next.next

O(1). Fails if the node is the last node.

---

Key Algorithms

Reversal (Recursive)

Recurse to the end; on the way back, set head.next.next = head; head.next = None. O(n) time, O(n) stack space. Returns the new head (the original tail).

Floyd's Cycle Detection

Slow/fast pointers meet inside the cycle iff one exists. To find the entry point: after the meeting, reset one pointer to head; advance both one step at a time; they meet at the cycle entry. O(n) time, O(1) space.

slow = n+xk+c

fast = n+yk+c

fast = 2*slow

n+c=(y-x)k=someintegertimesk

so, assume, n+c=k

Merge K Sorted Lists

Use a min-heap of (value, list_index, node) tuples. Pop minimum, push its successor. O(N log k) time where N = total nodes, k = number of lists. Divide-and-conquer pairwise merges achieves the same complexity with better cache behaviour.

Sort List

Merge sort: find middle (slow/fast), cut the list at mid (mid.next = None), sort each half recursively, merge. O(n log n) time, O(log n) stack space. Bottom-up merge sort reduces stack space to O(1).

Finding the Middle

Slow/fast two-pointer; O(n), O(1). Use fast = head to get the first middle; use fast = head.next to get the second middle for even-length lists.

Remove Nth from End

Advance fast N steps; move both until fast is null; slow is at the predecessor of the node to delete. Use a dummy head so removal of the first node works without special-casing.

Add Two Numbers (Digits in Reverse Order)

Digit-by-digit traversal with a carry variable. Treat missing nodes as contributing 0. Append an extra node if a final carry remains. O(max(m, n)) time.

Copy List with Random Pointer

Three-pass O(1)-space approach: (1) interleave clone nodes after originals, (2) set clone.random = original.random.next, (3) separate the two lists. Alternatively, a hashmap in O(n) space with two passes.

---

Advanced Techniques

In-Place Group Reversal

Solves problems asking to reverse every k nodes, reverse alternating k-groups, or reverse from position l to r repeatedly. Mechanism: track the group's pre-head and tail, apply iterative reversal for k steps, re-stitch to the previous segment's tail and the next group's pre-head. Use over a stack-based approach when O(1) space is required; use over full-list reversal when only a segment is targeted.

Weaving / Reorder List

Reorders to L0→Ln→L1→Ln-1→… in O(n) time, O(1) space: find middle, reverse second half in-place, interleave the two halves. Use over a deque or index-array approach when the interviewer requires O(1) extra space.

Palindrome Check via Half-Reversal

Reverse only the second half of the list in-place, compare with the first half node-by-node, then optionally restore. O(n) time, O(1) space. Use over a stack when O(1) space is required; restore the list after comparison if the problem guarantees the original structure must be preserved.

LRU Cache (Hash Map + Doubly Linked List)

O(1) get and put: the hash map provides O(1) node lookup by key; the doubly linked list provides O(1) insert-at-tail and O(1) delete-any-node. Sentinel head and tail nodes eliminate all boundary checks on insertion and deletion. Use when a problem asks for a fixed-capacity cache with recency-based eviction; a plain dict or OrderedDict is the Pythonic shortcut but interviewers often ask for the explicit implementation.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Empty list (head is None) — every algorithm that dereferences head.next or head.val crashes on null input. Guard at entry or use a dummy node so the real head is never null during surgery.

• Single-node list — reversal is a no-op but must still return the node, not null. Slow/fast cycle detection must check both fast and fast.next before advancing or fast.next.next raises an exception.

• Reversal pointer order — saving nxt = curr.next before curr.next = prev is mandatory. Reversing that assignment order loses the only reference to the rest of the list.

• Off-by-one in Nth from end — "Nth from end" is 1-indexed in most LeetCode problems. Advancing fast exactly N steps (not N−1) before the joint traversal is the invariant; verify on a 3-node list with N=1.

• Cycle causing infinite loops — algorithms that assume acyclicity (merge, sort, length counting) will loop forever on a cyclic list. Add cycle detection before applying non-cycle algorithms when input validity is not guaranteed.

• Even vs. odd length in middle-finding — the choice of fast = head vs. fast = head.next shifts which center node is returned for even-length lists. Palindrome check and reorder list require the second middle; verify which variant the algorithm needs.

• Not splitting the list before merge sort — when recursing on two halves, mid.next = None must be set after finding mid; otherwise the left-half call also processes the right half, causing incorrect results or infinite recursion.

• Losing the segment tail during group reversal — failing to save the pointer to the segment's tail before reversing leaves no way to re-stitch to the next segment.

• "Delete node given only itself" fails on last node — the value-copy trick (node.val = node.next.val; node.next = node.next.next) is undefined when the node is the tail. Confirm the problem guarantees this won't happen or handle separately.

---

Implementation Notes

• Python heapq cannot compare ListNode objects; for merge-k-sorted, push (node.val, list_index, node) tuples where list_index breaks ties without invoking ListNode.__lt__.
• Initialise dummy = ListNode(0); dummy.next = head rather than dummy.next = None when the sentinel must precede an existing list.
• For problems specifying in-place O(1) space, any auxiliary data structure (stack, array, dict) disqualifies the solution even if the algorithm is otherwise correct.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Merge / Sort

• Merge Two Sorted Lists (LC 21) — dummy head + iterative two-pointer merge
• Merge k Sorted Lists (LC 23) — min-heap or pairwise divide-and-conquer
• Sort List (LC 148) — merge sort; split with slow/fast, then merge

Structural Checks

• Palindrome Linked List (LC 234) — reverse second half, compare, optionally restore
• Intersection of Two Linked Lists (LC 160) — redirect pointers to the other head at null

Reorder / Arithmetic

• Reorder List (LC 143) — find middle, reverse second half, weave halves
• Rotate List (LC 61) — make list circular, then cut at the new tail
• Add Two Numbers (LC 2) — digit-by-digit traversal with carry
• Add Two Numbers II (LC 445) — digits in forward order

Clone

• Copy List with Random Pointer (LC 138) — interleave cloned nodes or use original-to-copy hash map

Design

• LRU Cache (LC 146) — doubly linked list + hash map
• Design Linked List (LC 707) — sentinel nodes simplify indexed insert/delete edge cases

Additional LeetCode Coverage

• Remove Duplicates from Sorted List II (LC 82) — dummy head; skip entire duplicate runs
• Remove Duplicates from Sorted List (LC 83) — single pass; link past repeated adjacent nodes
• Remove Linked List Elements (LC 203) — dummy head; delete nodes matching value during traversal
• Delete Node in a Linked List (LC 237) — copy next node's value, then bypass next node
• Odd Even Linked List (LC 328) — maintain separate odd/even chains, then concatenate
• Delete the Middle Node of a Linked List (LC 2095) — slow/fast with predecessor tracking
• Maximum Twin Sum of a Linked List (LC 2130) — reverse second half, then pairwise max sum
• Reverse Nodes in k-Group (LC 25) — reverse fixed-size groups and re-stitch boundaries
• Partition List (LC 86) — build before/after dummy chains, then join
• Insertion Sort List (LC 147) — sorted dummy prefix; insert each node into position

Clarification Questions to Ask

• Is the list guaranteed to be cycle-free? (If not, cycle detection must precede any traversal.)
• Is indexing 0-based or 1-based for positional operations?
• For "Nth from end," is N guaranteed to be within bounds?
• For group reversal (k-group), if the last group has fewer than k nodes, should it be reversed or left as-is?
• Is in-place modification required, or is O(n) extra space acceptable?
• For palindrome problems, must the original list structure be restored after checking?

Common Interview Mistakes

• Skipping the dummy head — candidates special-case head deletion instead of inserting a sentinel, leading to bug-prone conditionals that interviewers notice immediately.
• Reversal pointer assignment order — assigning curr.next = prev before saving nxt = curr.next drops the rest of the list; interviewers watch for this.
• Off-by-one in Nth from end — advancing fast N−1 instead of N steps is the most common single-line bug in this category.
• Not cutting the list at mid for merge sort — both recursive calls traverse the full list, causing infinite recursion or incorrect output.
• Confusing first and second middle — using the wrong fast-pointer initialisation breaks palindrome checks and reorder list for even-length inputs.
• Using a stack for palindrome when O(1) space is specified — a stack is O(n); interviewers who ask for O(1) space expect the reverse-second-half approach.

Typical Follow-Up Escalations

• "Now do it without recursion" → switch from recursive reversal to iterative three-pointer.
• "Now do it in O(1) space" → replace stack/array with in-place pointer surgery.
• "What if there might be a cycle in the input?" → prepend Floyd's cycle detection before the main algorithm.
• "Now sort the list" → merge sort in O(n log n) time; bottom-up variant for O(1) stack space.
• "What if it were a doubly linked list?" → identify which operations become cheaper (O(1) tail delete, O(1) delete-any-node) and which stay the same.
• "Scale to a billion nodes that don't fit in memory" → external merge sort (k-way merge of sorted runs from disk); skip lists for in-memory sorted access.