Linked-list manipulation

1 · Why linked lists matter — the intuition

Linked lists are the trade-off algorithm courses use to teach the idea that data structures have personalities. An array gives you constant-time random access (a[i] in O(1)) at the cost of O(n) inserts in the middle. A linked list gives you constant-time inserts and deletes at a known position (just rewire two pointers) at the cost of O(n) random access (no a[i]; you must walk from the head). One trade-off, two algorithms.

In production code, linked lists are almost never the right answer anymore. Hash maps beat them at lookup. Arrays beat them at iteration (better cache locality, no pointer chasing). Skip lists beat them at ordered insertion. Doubly-linked lists survive in one narrow niche: LRU caches, where the O(1) move-to-front operation is the right primitive. Everything else has a faster alternative.

So why do interviews still ask about them? Because writing correct pointer-manipulation code is the cleanest test of attention to detail that exists in coding interviews. There's no algorithmic insight to hide behind — just bookkeeping. Either you're rigorous about null checks, the order of pointer assignments, and the dummy-head trick, or you're not. The signal is unambiguous in 15 minutes of whiteboard time.

2 · How to recognise it — six distinct shapes

Linked-list problems usually announce themselves. The signal is in the input type — once you see ListNode, the question is which of the six recognisable shapes applies.

• The problem explicitly mentions a linked list. The most common signal. If the input is a ListNode, you're in this pattern.
• "Find the middle without knowing the length." Slow/fast pointers. Slow advances one, fast advances two; when fast hits the end, slow is at the middle.
• "Detect a cycle" or "find the cycle start". Floyd's tortoise and hare. The same slow/fast idea with a follow-up trick to locate the cycle entry.
• "Reverse in groups of k" or "reverse a sublist". A reverse loop wrapped in bookkeeping. Dummy head usually helps.
• "LRU cache" or "design a cache with O(1) operations". Doubly linked list plus hash map. The DLL gives O(1) move-to-front; the hash gives O(1) lookup.
• "Merge K sorted lists" or "merge two sorted lists". Dummy head plus comparison. K-way uses a heap or pairwise divide-and-conquer.

Shape A — reverse (in place or in groups)

The three-pointer dance: prev, curr, next_node. Save curr.next before overwriting, flip the link, advance. Variants: reverse the whole list (LC 206), reverse between positions left and right (LC 92), reverse in groups of k (LC 25). Group-reverse adds bookkeeping for "stitch the previous group's tail into the new head".

Shape B — cycle detection (Floyd's tortoise & hare)

Slow advances one, fast advances two. If they meet, there's a cycle. Phase two: reset one pointer to head, walk both at speed one; they meet at the cycle entry. Variants: LC 141 (just detect), LC 142 (find the entry), LC 287 "Find the Duplicate Number" (which secretly builds a cycle from array indices).

Shape C — merge two sorted

Dummy head plus comparison loop. Take the smaller head each iteration, append it to the dummy's tail, advance. Tail attaches the remaining non-empty list at the end. This is the atomic operation behind merge sort on lists (LC 148) and merge-K-sorted-lists (LC 23).

Shape D — find the kth node from the end

Two pointers, both starting at head. Advance the first k steps. Then advance both together until the first hits null. The second is now at the kth from the end. The trick: maintain a fixed "gap" between the two pointers. Variants: LC 19 "Remove Nth From End", LC 1721 "Swap Nodes in a Linked List".

Shape E — intersection of two lists

Two pointers, each starting at one head. When a pointer hits null, redirect it to the other list's head. After at most m + n steps, they meet at the intersection node (or both at null if disjoint). The clever observation: by switching heads, each pointer walks exactly m + n nodes, eliminating the length difference. Used in LC 160 "Intersection of Two Linked Lists".

Shape F — reorder / rearrange in place

Compositional. Find middle (Shape B's slow/fast). Reverse the second half (Shape A). Interleave (Shape C with a custom merge). Used in LC 143 "Reorder List", LC 234 "Palindrome Linked List" (find middle, reverse, compare), LC 86 "Partition List" (split into two, merge). The whole problem is composing the simpler tricks.

3 · Sister algorithms

Linked lists sit in a family of "linear-but-not-array" structures. Each cousin trades a different axis: Floyd's algorithm trades a hash set for O(1) space; Brent's trades comparisons for fewer pointer advances; skip lists trade simplicity for logarithmic search. Knowing the family stops you from defaulting to "linked list" when something cheaper exists.

• Floyd's tortoise & hare (1967). The slow/fast pointer trick — covered above. The original analysis is the classic example of O(1)-space cycle detection. Strong default for any "detect a cycle" question because the implementation is six lines and the proof is elegant.
• Brent's algorithm (1980). An alternative cycle-detection scheme. Where Floyd uses two pointers moving at different speeds, Brent uses one fixed and one walking, doubling the "teleport distance" each time the walker catches up. Empirically does fewer comparisons (≈36% fewer than Floyd in the average case) at the cost of slightly more bookkeeping. Niche but worth knowing exists; sometimes asked as a follow-up question after Floyd.
• Skip lists (Pugh, 1990). Probabilistic balanced BSTs built on linked lists. Each node has a stack of forward pointers — the "express lanes". Expected O(log n) search, insert, delete; much simpler to implement than a red-black tree. Used in Redis (sorted sets), LevelDB (memtable), Java's ConcurrentSkipListMap. The reason: skip lists are lock-free-friendly because most operations are local.
• Unrolled linked list. Each node holds an array of k elements instead of a single value. Better cache locality (most modern data lives in CPU caches; pointer-chasing is a 100+ cycle stall per node). Worse insert in the middle (have to split an array node). Used in some implementations of B-trees' leaf nodes and in real-time-graphics scene graphs.
• XOR linked list (only of historical / interview-trivia interest). Stores prev XOR next in a single pointer field, recovering one or the other by XORing with the known neighbour. Halves the pointer footprint of a doubly linked list at the cost of breaking standard debuggers and garbage collectors. Don't use it. Do remember it exists.
• Persistent (immutable) linked list. The standard cons-cell list of Lisp / Haskell / Clojure. Every "modification" returns a new list that shares structure with the old one — copy-on-write at the smallest possible granularity (one cell). The shape that makes functional programming's "immutable data" practical.

4 · Canonical example — Reverse Linked List (LC 206)

Problem. Given the head of a singly linked list, reverse the list and return the new head.

Input:  1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> null

Three pointers do the work: prev, curr, and a scratch next_node. At each step, save curr.next before you overwrite it, flip curr.next to point at prev, then advance both pointers one step. When curr falls off the end, prev is the new head. O(n) time, O(1) extra space.

5 · Reference implementation

The iterative reverse. Memorise this; it shows up everywhere.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr:
        next_node = curr.next   # SAVE next before you overwrite curr.next
        curr.next = prev        # flip the link
        prev = curr             # advance prev
        curr = next_node        # advance curr
    return prev                  # prev is the new head

Slow/fast pointers — the middle of a list in one pass.

def middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # for even length, returns the second middle

Floyd's cycle detection. If slow and fast meet, there's a cycle. To find the cycle start, reset one pointer to head and walk both one step at a time — they meet at the entry.

def detect_cycle(head: ListNode) -> ListNode | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # phase 2: find the cycle start
            ptr = head
            while ptr != slow:
                ptr = ptr.next
                slow = slow.next
            return ptr
    return None

Dummy head pattern for merge. Avoids special-casing the new head.

def merge_two(a: ListNode, b: ListNode) -> ListNode:
    dummy = ListNode()      # sentinel; never returned directly
    tail = dummy
    while a and 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 or b      # attach whichever is non-empty
    return dummy.next

5a · Reverse, frame by frame

The reverse loop is three pointer assignments per step. Drawn out, it's obvious; in code, it's the kind of thing that breaks at 2am if you don't have the diagram in your head. Three frames of reversing 1 → 2 → 3 → 4 → null:

5b · Floyd's cycle — step it yourself

Floyd's tortoise-and-hare for cycle detection is the kind of thing that feels like magic until you watch it happen. The animator below builds a list with an optional cycle and runs the slow/fast pointers — step through the inner loop to see slow and fast meet exactly inside the cycle, then watch the "reset to head and walk together" phase land both pointers at the cycle entry.

5c · The dummy-head pattern, explained once

Every operation that might modify the head of a list — insert, delete, merge, reverse-sublist — has two cases without a dummy: "this affects the head, so update head" vs "this affects something downstream, so update the predecessor's next pointer." Two cases is one bug waiting to happen.

A dummy (sentinel) node sits BEFORE the real head. Now every node has a predecessor, including what used to be the head. The two cases collapse into one: "update predecessor.next". At the end, return dummy.next — which is the (possibly new) head.

# Without dummy — head is special-cased
def remove_value(head, target):
    while head and head.val == target:
        head = head.next               # SPECIAL: removing the head
    if not head: return None
    prev, curr = head, head.next
    while curr:
        if curr.val == target:
            prev.next = curr.next      # GENERAL: removing downstream
        else:
            prev = curr
        curr = curr.next
    return head

# With dummy — one case
def remove_value(head, target):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == target:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next                  # might be original head, might not — same code

The dummy version is shorter, has no special case, and works correctly on inputs that the no-dummy version mishandles (e.g. [7, 7, 7] with target 7 — the original head is removed AND every subsequent node, which the no-dummy first loop has to anticipate).

6 · Variations

Seven shapes cover most of the territory. The pointer choreography differs but each one reduces to a couple of the four base tricks.

7 · Five-problem progression

8 · Three more worked problems

Three problems chosen to exercise three different combinations of the six shapes. Solve each from a blank page before reading the walkthrough — for linked lists, the second time you write the code feels qualitatively different from the first.

8a · LC 142 — Linked List Cycle II (find the cycle start)

Problem. Given a linked list, return the node where the cycle begins. Return null if there's no cycle. O(n) time, O(1) space.

Phase 1: standard Floyd's slow/fast — if they meet, there's a cycle. Phase 2: reset one pointer to head, walk both at speed 1; they meet at the cycle entry. The proof is in the callout below the animator above; the code is short.

// ListNode is the standard singly-linked node type.
type ListNode struct {
    Val  int
    Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            // PHASE 2: find the cycle entry
            ptr := head
            for ptr != slow {
                ptr = ptr.Next
                slow = slow.Next
            }
            return ptr
        }
    }
    return nil
}

8b · LC 25 — Reverse Nodes in K-Group

Problem. Reverse the nodes of a linked list k at a time. If the number of remaining nodes is not a multiple of k, leave them as is. Do it in place.

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 2 -> 1 -> 4 -> 3 -> 5

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5

The bookkeeping is where the bugs live. Strategy: dummy head, walk a groupPrev pointer along; for each group, first check k remaining nodes exist; reverse exactly k; stitch groupPrev to the new head, advance groupPrev to the new tail (which is the old head of the reversed group).

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next: head}
    groupPrev := dummy

    for {
        // Find the kth node from groupPrev; nil means too few left
        kth := groupPrev
        for i := 0; i < k && kth != nil; i++ {
            kth = kth.Next
        }
        if kth == nil {
            break
        }
        groupNext := kth.Next

        // Reverse the group: from groupPrev.Next up to and including kth
        prev, curr := groupNext, groupPrev.Next
        for curr != groupNext {
            next := curr.Next
            curr.Next = prev
            prev = curr
            curr = next
        }

        // Stitch: groupPrev now points to the reversed group's new head (= kth)
        // The reversed group's new tail (= original groupPrev.Next) is the next groupPrev
        tmp := groupPrev.Next
        groupPrev.Next = kth
        groupPrev = tmp
    }
    return dummy.Next
}

8c · LC 23 (HARD) — Merge K Sorted Lists with min-heap

Problem. You are given an array of k linked-lists, each sorted in ascending order. Merge all into one sorted linked list and return it.

The two solutions: (1) pairwise divide-and-conquer using the merge-two template O(N log k); (2) min-heap of the k current heads, repeatedly pop the smallest and push its successor. Same complexity, different constants. The heap version is more general (extends to merging sorted streams of unknown length).

import "container/heap"

// nodeHeap satisfies heap.Interface, keyed on Val.
type nodeHeap []*ListNode

func (h nodeHeap) Len() int            { return len(h) }
func (h nodeHeap) Less(i, j int) bool  { return h[i].Val < h[j].Val }
func (h nodeHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *nodeHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    h := &nodeHeap{}
    heap.Init(h)
    for _, l := range lists {
        if l != nil {
            heap.Push(h, l)
        }
    }

    dummy := &ListNode{}
    tail := dummy
    for h.Len() > 0 {
        node := heap.Pop(h).(*ListNode)
        tail.Next = node
        tail = tail.Next
        if node.Next != nil {
            heap.Push(h, node.Next)
        }
    }
    return dummy.Next
}

9 · How to solve hard linked-list problems, step-by-step

Linked lists reward discipline. Five rules, in order, that catch most pointer bugs before the first compile.

Step 1 — Use a dummy head whenever the head might change

Any operation that could remove, insert, or replace the first node: dummy head. The cost is one node; the benefit is removing every "is this the head?" branch. Return dummy.Next at the end. Even when the head can't change, a dummy head often makes the loop body uniform — that uniformity is the whole point.

Step 2 — Two pointers (fast / slow) for "find a position relative to length"

Any "find the middle", "kth from the end", "halfway between two pointers" can be done in a single pass with two pointers. The pattern: maintain a fixed offset (for kth-from-end) or a 2x speed ratio (for middle / cycle). The list length is never directly known; the relationship between the pointers does the bookkeeping for you.

Step 3 — Reverse subsections only when you have a stable "before" pointer

Reversing destroys structural context: after the reverse, head is now the tail; tail is now somewhere in the middle. Always have a pointer to the node before the section you're reversing (the dummy head is your default). Save the node after the section before starting — without both anchors, you can't stitch the reversed segment back in.

Step 4 — Draw the pointer manipulation on paper before coding

Three or four nodes on a whiteboard. Arrows for next. Label every pointer: prev, curr, next_node, tail. Walk through one iteration with a pen, redrawing the arrows as you go. Most linked- list bugs are visible the moment you draw them — the keyboard hides them. This is the single highest-yield activity in linked-list problems.

Step 5 — Test on length 0, 1, 2, and 3 explicitly

Empty list, single node, two nodes, three nodes — those are the cases where the off-by-ones live. A solution that works on length 5 but fails on length 1 is the most common kind of linked-list bug. If you have time for one extra test, add "list with a cycle" — Floyd's- adjacent problems fail in interesting ways on length-1 cycles.

10 · A diagram — Floyd's cycle, two phases

The two-phase structure of Floyd's algorithm, drawn out so the "reset to head" trick stops feeling like magic:

The animation in section 5b above lets you step the algorithm interactively. The diagram here is the formal version of why it works — annotated with the distances L, C, and k from the proof. Once you've matched the proof to the animation once, the algorithm becomes muscle memory.

11 · Common pitfalls — and the pointer bugs everyone writes once

• Forgetting the dummy head. You end up special-casing the head node over and over: every insert, every delete, every merge gets an "if this is the head, do this instead" branch. A sentinel removes all of them.
• Losing the next pointer before reassignment. The classic reverse bug. Always do next_node = curr.next FIRST, then flip curr.next = prev. Reverse those two lines and you've severed the rest of the list.
• Null-pointer access at the end. The slow/fast loop condition is while fast and fast.next, not while fast.next. Drop either check and even-length or empty lists crash.
• Reversing twice and getting back to the start. An off-by-one in the loop bound — usually iterating one too few or one too many times. Trace a list of length 2 and 3 on paper before submitting.
• Confusing Floyd's cycle detection. Fast moves two nodes per iteration; when slow and fast meet, the distance from head to cycle-start equals the distance from the meeting point to cycle-start (going forward). That's why resetting one pointer to head and walking both at speed 1 lands them at the entry. It's not obvious; if you don't believe it, prove it once and move on.
• Forgetting to update tail in the merge loop. If tail = tail.next is missing, every comparison overwrites the same slot and you end up with a list of length 1.
• Losing reference to next when rewiring multiple links in a single step. Beyond the basic reverse, this hits in reorder-list, partition, and reverse-in-groups. Rule: every line that writes to a .next field must be preceded by a save of that field's old value (if you need it later). Linters won't catch this; only experience will.
• Off-by-one in length counts. "Find the kth from end with k=length" should return the head; "k=1" should return the tail. If you advance the fast pointer k steps when you should advance k+1 (or vice versa), the slow pointer lands one off. Trace on length 3 with k=1, k=2, k=3 before submitting.
• Forgetting null checks on the second-to-last node. When you walk to "the node before the last", the loop is while node.Next != nil && node.Next.Next != nil. Drop either check and you'll dereference null on lists of length 1 or 2. Easy to write and ship as while node.Next != nil by accident.
• Infinite loop from accidental cycle creation. When you set a.Next = b, if b is somewhere upstream of a in the list, you've just created a cycle. The next traversal will spin forever. This is most common in reorder/rearrange problems — make sure the node you're attaching forward to isn't already pointing back. Set the tail's Next to nil as the very last step of any in-place rearrangement.
• Double-free via shared sub-lists. If you split a list into two pieces and forget to terminate the first piece with nil, both halves still share the tail. Any later modification to one half corrupts the other. The fix: explicit prev.Next = nil immediately after splitting.
• Confusing "the node" with "the value at the node". In Python the distinction is fuzzy; in Go and C++ it's the difference between node and node.Val. Comparing nodes is identity (pointer equality); comparing values is what most algorithms actually want. LRU caches in particular store node pointers, not values — confuse the two and the eviction list desyncs from the hash map.

12 · What to say in the interview

1. "This is the linked-list pattern — one of the four tricks." Name them: two-pointer, reverse, merge, dummy head. Then say which one(s) apply.
2. Draw the pointer diagram. Sketch three or four nodes with arrows. Walk through one iteration on the board before writing code. Most pointer bugs are visible the moment you draw them.
3. "I'll use a dummy head." Say it out loud whenever you might modify the head. It signals you've seen the special-case trap and stepped around it.
4. "O(n) time, O(1) extra space." The usual bound for in-place pointer work. Worth stating; the interviewer is listening for it.
5. Edge cases to mention. Empty list, single node, two nodes, list with a cycle, even vs odd length (matters for "middle"), and duplicates in sorted-merge inputs.

13 · Where this gets asked

14 · Try it yourself

Reverse Linked List · LC 206

The minimal pointer-juggling drill. Hint: three pointers — prev, curr, next_node. Save curr.next BEFORE you overwrite it. Then practise the recursive version too — recursion makes the invariant easier to see.

Merge Two Sorted Lists · LC 21

The dummy-head template. Hint: dummy = ListNode(), tail = dummy, append the smaller head each iteration, then attach whichever list is non-empty at the end. Return dummy.next.

Reverse Linked List II · LC 92

Reverse a sublist between positions left and right. Hint: use a dummy head and walk to position left-1. Then do a standard reverse for right - left + 1 nodes; finally stitch the three pieces back together.

LRU Cache · LC 146

The classic DLL + hash combo. Hint: every key in the hash maps to a DLL node. get moves the node to the front; put inserts at the front and evicts the tail if at capacity. Sentinel head + sentinel tail simplify edge cases.

Stretch — Reverse Nodes in K-Group · LC 25

The bookkeeping is where the bugs hide. Hint: write a helper that reverses exactly k nodes and returns the new head + tail. Then loop: check there are k remaining nodes, reverse, stitch the previous group's tail into the new head. Dummy head saves you here.

Further reading

• CLRS — Section 10.2. The textbook treatment of linked lists with sentinels. Worth reading once for the dummy-head argument written out formally.
• Sedgewick & Wayne — Algorithms, Section 1.3. Gentler treatment with cleaner code. The bag/queue/stack implementations all rely on the same pointer choreography.
• Adjacent: Two pointers. Same idea applied to arrays. Once you have the linked-list version, the array version is a coordinate swap.
• Adjacent: Hash map. The other half of the LRU cache. Hash-to-DLL-node is the combo that makes O(1) get/put work.
• Semicolony: Linked-list cycle simulator. Visualises slow/fast pointers chasing each other through a cycle. Worth a few minutes to see why Floyd's reset-and-walk trick lands at the entry.