Linked Lists

Linked lists are a fundamental data structure tested heavily at FAANG and quant firms. Mastery requires internalizing fast/slow pointer tricks, in-place reversal without extra space, cycle detection via Floyd's algorithm, and building complex structures like LRU cache. These problems reward pointer manipulation fluency above all else.

Python classes / object referencesBig-O notationHash mapsFast/Slow PointersFloyd's Cycle DetectionIn-Place ReversalDummy NodeTwo PointersLRU Cache

Core Concepts

1Iterative reversal: the canonical three-pointer technique maintains prev=None, curr=head, and next_node. At each step: save next_node = curr.next, point curr.next = prev, advance prev = curr, advance curr = next_node. After the loop, prev is the new head. The key insight is that you never lose access to the remaining list because you save next_node before overwriting curr.next. Time O(n), Space O(1). Reversing a sublist (LC 92) extends this: find the node just before the reversal range, then run the reversal for exactly m steps, then reconnect.
2Recursive reversal: base case is head is None or head.next is None — return head. Recursively reverse the rest of the list: new_head = reverse(head.next). After the recursive call, head.next.next = head (make the next node point back to head), head.next = None (sever head's forward pointer). The recursion unwinds from the tail, reversing pointers as it returns. Elegant but uses O(n) stack space — prefer iterative in interviews unless recursion is explicitly requested.
3Fast/slow pointers (Floyd's algorithm) for cycle detection: slow moves one step per iteration, fast moves two. If a cycle exists, fast will eventually lap slow inside the cycle and they will meet. If fast reaches None, there is no cycle. Time O(n), Space O(1). Intuition: if there is a cycle of length c, once both pointers are in the cycle, fast gains one step on slow per iteration, so they meet after at most c iterations.
4Finding the cycle start: after Floyd's detection (slow == fast inside cycle), reset one pointer to head and leave the other at the meeting point. Advance both one step at a time. Where they meet again is the cycle start. Mathematical proof: let F = steps to cycle entry, C = cycle length, k = meeting point offset from cycle start. We can show F + a = n*C, so F = n*C - a. The reset pointer travels F steps to reach the cycle entry. The meeting-point pointer is a steps from the cycle entry and travels n*C - a = F more steps to also reach the cycle entry. They arrive simultaneously.
5Finding the middle of a linked list: use fast/slow pointers starting at head. Advance slow one step and fast two steps each iteration. When fast reaches None (even-length) or fast.next is None (odd-length), slow is at the middle. For merge sort on linked lists, stop when fast.next is None or fast.next.next is None to get the left-middle. For palindrome check, you want to split after the middle.
6Remove Nth node from end: use two pointers starting at a dummy node prepended to the list. Advance fast n+1 steps ahead of slow. Then advance both until fast reaches None. At this point slow.next is the target node — set slow.next = slow.next.next. The dummy node handles the edge case where the head is the node to remove. Why n+1? So slow lands on the node BEFORE the target.
7Merging sorted lists: use a dummy head and a current pointer. At each step, compare the heads of both lists and attach the smaller one. Advance the pointer of the list you just consumed. When one list is exhausted, attach the remaining tail of the other directly. Time O(m+n), Space O(1). For merging k sorted lists (LC 23), use a min-heap of (value, index, node) tuples — O(N log k) where N is total nodes.
8LRU Cache with O(1) get and put: combine a doubly-linked list and a hash map. The list maintains recency order (most recent at head, least recent at tail). The hash map maps key to node for O(1) access. On get: look up node in map, move it to head, return value. On put: if key exists, update value and move to head. If at capacity, remove the tail node from both list and map, then insert new node at head. Use dummy head and tail sentinel nodes to eliminate all null-pointer edge cases.

Key Patterns & Templates

Iterative reverse: prev=None; while curr: nxt=curr.next; curr.next=prev; prev=curr; curr=nxt; return prev

Fast/slow middle: slow=fast=head; while fast and fast.next: slow=slow.next; fast=fast.next.next

Floyd cycle detect: while fast and fast.next: slow=slow.next; fast=fast.next.next; if slow==fast: cycle

Cycle start: reset one to head, keep other at meeting point; advance both one step; meet at cycle entry

Remove Nth from end: dummy→head; fast n+1 ahead of slow; advance both; slow.next=slow.next.next

Merge two sorted: dummy=ListNode(0); cur=dummy; while l1 and l2: attach smaller, advance that list

LRU Cache: dict[key]→node + doubly-linked list; get/put O(1) via move-to-head and evict-tail

Dummy node pattern: prepend ListNode(0) before head to avoid special-casing head modifications

Worked Examples

Given a linked list 1→2→3→4→5, reorder it to 1→5→2→4→3 in-place. More generally: L0→L1→Ln-1→Ln becomes L0→Ln→L1→Ln-1→…

1Step 1 — Identify the three-step structure: (1) find the middle to split into two halves, (2) reverse the second half, (3) interleave the two halves. All O(1) space. No new nodes created.

2Step 2 — Find middle: use fast/slow pointers with termination when fast.next is None or fast.next.next is None. This gives us the LEFT middle, so the first half is at least as long. For 1→2→3→4→5, slow stops at 3.

3Step 3 — Split: save second_half = slow.next, then slow.next = None to sever the list. First half is 1→2→3 and second half (to be reversed) is 4→5.

4Step 4 — Reverse second half: use the standard iterative reversal. 4→5 becomes 5→4.

5Step 5 — Interleave: two pointers p1=head of first half, p2=head of reversed second half. Each step: save p1_next=p1.next and p2_next=p2.next; set p1.next=p2; set p2.next=p1_next; advance p1=p1_next, p2=p2_next. Stop when p2 is None (second half exhausted).

6Step 6 — Verify: 1→2→3 interleaved with 5→4 gives 1→5→2→4→3. Time O(n), Space O(1).

✓ Time O(n), Space O(1). The decomposition into three sub-problems (find middle, reverse half, interleave) is the key insight. Each sub-problem is a classic technique independently — the novelty is composing them. Interleaving must stop when the second pointer is None, not the first, because the first half can be one node longer than the second.

Common Mistakes

⚠

Losing the rest of the list during reversal: always save nxt = curr.next BEFORE setting curr.next = prev. This is the single most common linked list bug. Without saving nxt, you permanently lose access to the rest of the list. Developing the muscle memory of 'save, reverse, advance' prevents this.

⚠

Off-by-one in fast pointer initialization for Nth-from-end: advancing fast exactly n steps (not n+1) means slow ends up ON the target node, not BEFORE it. You cannot then do slow.next = slow.next.next. Use a dummy node before head and advance fast n+1 times from the dummy — slow lands on the node before the target.

⚠

Cycle detection: not handling the case where fast or fast.next is None before accessing fast.next.next. Always write 'while fast and fast.next: fast = fast.next.next'. Accessing fast.next.next without guarding fast.next is a null pointer exception. Similarly, using 'if slow == fast' on the first iteration catches nothing — the loop body must run at least once before checking.

⚠

LRU Cache: forgetting to delete the old node from both the map AND the list on put when key already exists. If you only update the map and insert a new list node, you create a ghost node in the list that never gets evicted, and the eviction logic will eventually remove the wrong node. Always _remove the existing node before _insert_front on an update.

Back to SWE Hub