Linked Lists

Why this pattern exists / recognition signals

An array is a contiguous block of memory: indexing is O(1) because address = base + index * size, but inserting or deleting anywhere except the end means shifting every element after it — O(n). A linked list gives up contiguous storage (and O(1) indexing) in exchange for O(1) insert/delete at a node you already hold a reference to — no shifting, just rewiring a couple of pointers.

Recognition signals — reach for linked-list thinking when the problem says:

“reverse a list” / “reverse in groups of k” → pointer rewiring
“detect a cycle” / “find the start of a loop” / “find the middle” → fast/slow (Floyd’s) pointers
“merge k sorted lists” / “merge two sorted lists” → pointer-following, often paired with a dummy head
You’re asked to do it “in O(1) extra space” — arrays generally can’t rearrange without an auxiliary array; a linked list can rewire pointers in place
The input is explicitly a ListNode-style structure rather than an array

The recurring simplifying trick across almost all of these: a dummy head node. Any operation that might need to change the head of the list (deleting the first node, merging into a new list, reversing) has an annoying special case — “is this the head?” — for every real node. A dummy node sitting before the real head turns “the head might change” into “just look at dummy.next at the end”; every node, including the first, is now some_node.next of something, so insert/delete logic is uniform with no special-cased first node.

Core mechanism

Why O(1) insert/delete at a known node beats an array

flowchart LR
    subgraph Array["Array: insert 'X' at index 1"]
        direction LR
        A0["idx0: A"] --> A1["idx1: B"] --> A2["idx2: C"] --> A3["idx3: D"]
        Note1["Every element from index 1 onward
must shift right by one slot: O(n)"]
    end

flowchart LR
    subgraph List["Linked list: insert 'X' after node A"]
        direction LR
        L0["A"] -->|next| L1["B"] --> L2["C"] --> L3["D"]
        Note2["Only A.next and X.next are rewritten.
B, C, D never move: O(1)"]
    end

The catch: that O(1) is only true if you already hold a reference to the node before the insertion point. Finding a node by value or position is still O(n) (no random access) — the win is specifically “insert/delete once you’re already there,” e.g. while iterating.

Iterative reversal: prev / curr / next

Reversing a singly linked list in place means, for every node, flipping its next pointer to point backward instead of forward. You need three pointers because once you overwrite curr.next, you’d lose the rest of the list unless you saved it first.

flowchart LR
    subgraph Before["Before: 1 -> 2 -> 3 -> null, prev=null, curr=1"]
        direction LR
        P1["prev: null"]
        N1["1 (curr)"] --> N2["2"] --> N3["3"] --> N4["null"]
    end

flowchart LR
    subgraph Step["One iteration: save next, flip curr.next, advance both"]
        direction LR
        S1["next = curr.next  (save '2' before we lose it)"]
        S2["curr.next = prev  (1 now points back to null)"]
        S3["prev = curr        (prev advances to 1)"]
        S4["curr = next        (curr advances to 2)"]
        S1 --> S2 --> S3 --> S4
    end

After the loop finishes (curr becomes null), prev is sitting on the new head. This is the single pattern to internalize: save next before you overwrite curr.next, then walk both pointers forward.

Floyd’s cycle detection (tortoise and hare)

A slow pointer moves one step at a time, a fast pointer moves two. If there’s no cycle, fast (or fast.next) hits null and you’re done — no cycle. If there is a cycle, the claim is fast is guaranteed to catch slow — here’s why.

Once slow enters the cycle, think of the situation from fast’s point of view as “closing a gap” on slow every step. Each step, fast gains exactly one node of ground on slow (fast moves 2, slow moves 1, net gap closure = 1). The gap starts at some non-negative integer size ≤ (cycle length − 1) and shrinks by exactly 1 each step — it can only hit 0 (a meeting) or wrap around; it can never jump over slow, because it closes by exactly 1 node per step and the cycle is discrete. So a meeting is mathematically guaranteed within at most one full loop around the cycle.

Finding the cycle’s start (the classic follow-up): let the distance from the head to the cycle’s start be a, and the distance from the cycle’s start to the meeting point be b, and the remaining cycle length back to the start be c (so cycle length = b + c).

When they meet: slow has traveled a + b. Fast has traveled a + b + k(b+c) for some integer k ≥ 1 (it lapped the cycle k extra times), and fast traveled exactly twice as far as slow: 2(a+b) = a + b + k(b+c) → a + b = k(b+c) → a = k(b+c) - b = (k-1)(b+c) + c.
That last form says: a is exactly c plus some whole number of full laps. So if you place one pointer back at the head and leave the other at the meeting point, and advance both one step at a time, they’ll both reach the cycle’s start at the same time — the head-pointer walks a steps to reach the start, the meeting-point pointer walks a steps too (which is c plus whole laps, landing back exactly at the start).

flowchart LR
    H["head"] --> N1["a nodes"] --> S["cycle start"]
    S --> N2["b nodes"] --> M["meeting point"]
    M --> N3["c nodes"] --> S

Worked numeric example — reverse a linked list

Input: 1 -> 2 -> 3 -> null

Step	prev	curr	curr.next before	action	list state (via prev/curr)
init	null	1	2	—	1→2→3→null
1	null	1	2	next=2; 1.next=null; prev=1; curr=2	null←1 2→3→null
2	1	2	3	next=3; 2.next=1; prev=2; curr=3	null←1←2 3→null
3	2	3	null	next=null; 3.next=2; prev=3; curr=null	null←1←2←3
end	3	null	—	loop exits (curr==null)	return prev (3→2→1→null)

Worked numeric example — cycle detection and start

List: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (5 points back to 3, so a=2 (nodes 1,2 before the cycle), cycle is 3->4->5->3, cycle length 3).

Step	slow (×1)	fast (×2)	met?
0	1	1	no
1	2	3	no
2	3	5	no
3	4	4 (5→3→4)	yes, meeting point = 4

Now reset one pointer to head (node 1), keep the other at the meeting point (node 4), advance both one step at a time:

Step	head-pointer	meeting-pointer
0	1	4
1	2	5
2	3	3

Both land on node 3 after 2 steps — the cycle’s start, matching a = 2.

Java — representative implementations

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
 
public class LinkedListOps {
 
    // Iterative reversal: prev/curr/next
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // save before we overwrite
            curr.next = prev;          // flip the pointer
            prev = curr;                // advance prev
            curr = next;                 // advance curr
        }
        return prev; // prev is the new head once curr runs off the end
    }
 
    // Floyd's cycle detection + find the start of the cycle
    public ListNode detectCycleStart(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // cycle found; now find the entry point
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr; // cycle start
            }
        }
        return null; // no cycle
    }
 
    // Merge two sorted lists using a dummy head
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2; // splice in whatever remains
        return dummy.next; // real head, no special case needed
    }
}

Python — representative implementations

from typing import Optional
 
 
class ListNode:
    def __init__(self, val: int = 0, next: "Optional[ListNode]" = None):
        self.val = val
        self.next = next
 
 
def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    """Iterative reversal: prev/curr/next."""
    prev, curr = None, head
    while curr is not None:
        next_node = curr.next   # save before we overwrite
        curr.next = prev         # flip the pointer
        prev = curr               # advance prev
        curr = next_node           # advance curr
    return prev  # prev is the new head once curr runs off the end
 
 
def detect_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
    """Floyd's cycle detection + find the start of the cycle."""
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            ptr = head
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr  # cycle start
    return None  # no cycle
 
 
def merge_two_lists(
    l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
    """Merge two sorted lists using a dummy head."""
    dummy = ListNode()
    tail = dummy
    while l1 is not None and l2 is not None:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 if l1 is not None else l2  # splice in whatever remains
    return dummy.next  # real head, no special case needed

Complexity comparison

Operation	Array	Singly linked list	Doubly linked list
Access by index	O(1)	O(n)	O(n)
Search by value	O(n)	O(n)	O(n)
Insert/delete at known node	O(n) (shift)	O(1) (forward only, need prev pointer)	O(1)
Insert/delete at head	O(n)	O(1)	O(1)
Insert/delete at tail (no tail ref)	O(1) amortized	O(n) (must walk to find it)	O(1) with tail pointer
Reverse	O(n), needs O(n) extra space or careful in-place swap	O(n) time, O(1) space	O(n) time, O(1) space
Cycle detection	N/A (no “next” concept)	O(n) time, O(1) space (Floyd’s)	O(n) time, O(1) space
Extra memory per element	none	one pointer	two pointers

Common pitfalls

Losing the rest of the list on reversal: overwriting curr.next before saving it into a next variable orphans everything after curr — always save-then-flip, never flip-then-save.
Off-by-one on the dummy head: returning dummy instead of dummy.next returns a list with a bogus 0/sentinel value prepended.
Null pointer on fast.next.next: the loop condition must check both fast != null and fast.next != null — checking only fast != null crashes when the list has an even number of nodes and fast lands exactly on the last node.
Confusing “detect a cycle” with “find its start”: detecting only needs the meeting point; finding the start needs the second phase (reset one pointer to head, advance both by one) — a very common half-answer in interviews.
Losing the head reference while traversing: iterating with the same variable that started as head (instead of a separate curr) makes the original list unreachable — always traverse with a copy.
Forgetting to null-terminate: after reversal, the original head’s next must end up null (it becomes the new tail) — if you never set it, you can accidentally leave a stale forward pointer that creates a cycle.

Practice problems

Reverse Linked List (iterative and recursive)
Reverse Linked List II (reverse only a sub-range, in place)
Linked List Cycle (detect only)
Linked List Cycle II (detect + return the start node)
Merge Two Sorted Lists (dummy head)
Merge k Sorted Lists (heap or divide-and-conquer over the pairwise merge)
Remove Nth Node From End of List (two pointers, one offset by n, dummy head to handle removing the actual head)
Reorder List (find middle via fast/slow, reverse second half, merge alternately)
Copy List with Random Pointer (interleaving trick or hash map)

Interview angles

“Why must fast catch slow if a cycle exists — prove it, don’t just assert it.” — frame it as a closing gap: once both pointers are inside the cycle, fast closes the distance to slow by exactly one node per step, and a gap that shrinks by exactly 1 each step from a finite starting value can’t skip over 0 — it must hit it.
“How do you find where the cycle starts, not just that one exists?” — reset one pointer to head, leave the other at the meeting point, advance both one step at a time; they meet at the cycle’s start. Be ready to derive why with the a = (k-1)(b+c) + c algebra, not just recite the trick.
“Can you reverse a linked list without extra space, and what’s the recursive version’s actual space cost?” — iterative is O(1) space; recursive is O(n) space from the call stack even though no explicit data structure is allocated — a common trap when someone claims recursion is “still O(1).”
“Why is deleting a node from the middle of a singly linked list awkward if you’re only given that node (not the head)?” — you can’t null out its own next and rewire the previous node’s pointer, because you have no back-reference in a singly linked list; the common workaround (copy the next node’s value into this node, then delete the next node) only works if it’s not the tail.
“When would you pick a doubly linked list over singly, given it costs an extra pointer per node?” — whenever you need O(1) deletion given only a node reference (no head walk needed to find “prev”), e.g. an LRU cache’s internal list.
“Why does an interviewer ask you to solve this with O(1) extra space?” — it rules out “copy into an array, reverse the array, rebuild the list” style answers and forces you to demonstrate actual pointer manipulation, which is the skill being tested.

Notes

Explorer