09 — Linked List

What a linked list is

An array stores elements in one contiguous block, so arr[5] is instant arithmetic. A linked list stores each element in its own node, and each node holds a pointer to the next:

head
 ↓
[1|•]──→[2|•]──→[3|•]──→[4|null]

The trade:

Linked list questions are pointer-choreography tests. There's rarely a clever algorithm; there's a sequence of reassignments that must happen in the right order, plus edge cases at the head and tail.

Two devices remove nearly all the pain: the dummy head and the fast/slow pointer pair.

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Device 1 — the dummy head

The problem it solves

Any operation that might modify the first node becomes a special case, because the first node has no predecessor to repoint:

// deleting a node normally:
prev.next = node.next;        // needs prev

// deleting the FIRST node:
head = head.next;             // completely different code

The fix

Put a fake node in front. Now every real node has a predecessor, so one code path handles all of them:

dummy
  ↓
[ * |•]──→[1|•]──→[2|•]──→[3|null]

ListNode dummy = new ListNode(0, head);
ListNode prev = dummy;
// ... operate uniformly; prev.next is always "the node I might replace"
return dummy.next;     // NOT head

Returning head instead of dummy.next is the classic bug. If the first node was removed or the list was reordered, head points at something that's no longer first. dummy.next is always correct by construction.

Use a dummy whenever you're: deleting nodes, merging lists, building a new list, or partitioning.

Device 2 — fast and slow pointers

Two pointers, one moving twice as fast. Three standard results fall out.

Finding the middle

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow is now at the middle

Why it works: when fast has travelled 2k steps, slow has travelled k. When fast hits the end (2k = n), slow is at n/2.

Trace on 1→2→3→4→5:

The even-length variant matters. On 1→2→3→4, this version lands slow on 3 (the second of the two middles). Starting with fast = head.next instead lands it on 2 (the first middle) — which is what Reorder List needs, because it must split before the second half. Know which you need and say why.

Both null checks are required: fast != null guards odd lengths, fast.next != null guards even ones. Dropping either throws a NullPointerException.

Cycle detection (Floyd's algorithm)

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}
return false;

Why they must meet if a cycle exists: once both are inside the cycle, fast gains exactly one position on slow per step. So the gap between them shrinks by 1 each step: 5, 4, 3, 2, 1, 0. It cannot jump over — a gap of 1 becomes 0 on the very next step. Within at most c steps (the cycle length) they collide.

Compare with == (same object), not .equals (same value) — two different nodes can hold the same value.

Finding where the cycle starts

ListNode slow = head, fast = head;
do {
    slow = slow.next;
    fast = fast.next.next;
} while (slow != fast);

slow = head;                       // restart ONE pointer at the head
while (slow != fast) {
    slow = slow.next;
    fast = fast.next;              // now both move at the SAME speed
}
return slow;                       // the cycle's entry node

Why this works — the arithmetic:

head ──a──→ [entry] ──b──→ [meeting point]
              ↑                   │
              └────────c──────────┘

Let a = distance from head to the cycle entry, b = entry to meeting point, c = meeting point back around to entry. Cycle length is b + c.

At the meeting: slow has walked a + b. fast has walked twice that, 2(a + b), and the extra distance it covered is whole laps of the cycle:

2(a + b) - (a + b) = a + b = k(b + c)     for some whole number k

So a + b is a multiple of the cycle length. Therefore a = k(b+c) - b, which means: walking a steps from the head, and a steps from the meeting point, land on the same node — the entry.

You don't need to reproduce the algebra live; you need the conclusion ("a and b are congruent modulo the cycle length, so two same-speed walkers meet at the entry").

Find the Duplicate Number is exactly this. Treat nums[i] as "the next pointer of node i". Since values are in [1, n] and there are n+1 of them, following pointers must eventually revisit a node — and the duplicate value is the cycle entry, because two different indices point into it. Explaining that mapping is the question; the code is the snippet above.

Nth node from the end — a fixed gap

Not a speed difference this time, but a constant offset:

ListNode dummy = new ListNode(0, head);
ListNode fast = dummy, slow = dummy;

for (int i = 0; i < n; i++) fast = fast.next;     // open a gap of n

while (fast.next != null) {                        // advance together
    fast = fast.next;
    slow = slow.next;
}
slow.next = slow.next.next;                        // slow is the target's PREDECESSOR
return dummy.next;

Why anchoring both at dummy: it guarantees slow ends on the node before the target, even when the target is the head. Without the dummy, removing the first node needs separate code.

Trace: remove the 2nd from the end of 1→2→3→4→5.

After the gap loop (n = 2): slow at dummy, fast at node 2. Advance together until fast.next == null: fast at 5, slow at 3. slow.next = slow.next.next → node 3 now points to node 5, skipping 4. ✓

Reversal

The three-pointer walk

ListNode prev = null, cur = head;
while (cur != null) {
    ListNode next = cur.next;    // 1. SAVE what comes next (we're about to destroy the link)
    cur.next = prev;             // 2. FLIP this node's pointer backwards
    prev = cur;                  // 3. advance prev
    cur = next;                  // 4. advance cur
}
return prev;                     // prev is the new head; cur is null

Why the save on line 1 is mandatory: line 2 overwrites cur.next. Without saving it first, you lose the entire rest of the list.

Trace on 1→2→3:

Return prev = node 3. ✓

Memorize the order of those four lines. Re-deriving them under pressure wastes time you need elsewhere.

Recursive form

ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;   // empty or single node
    ListNode newHead = reverse(head.next);                // reverse everything after me
    head.next.next = head;                                // the node ahead now points BACK to me
    head.next = null;                                     // sever my old forward link
    return newHead;
}

Reading head.next.next = head: head.next is the node immediately after me. Setting its next to me flips that one link. The recursive call has already handled everything beyond.

Elegant, but O(n) stack depth. For n = 10^5 the iterative version is the responsible choice — mention that.

Reverse Nodes in K-Group

Composes reversal with a dummy head and a "does a full group remain?" check.

ListNode dummy = new ListNode(0, head);
ListNode groupPrev = dummy;

while (true) {
    // 1. Is there a full group of k ahead?
    ListNode kth = groupPrev;
    for (int i = 0; i < k && kth != null; i++) kth = kth.next;
    if (kth == null) break;                     // fewer than k remain — leave them alone

    ListNode groupNext = kth.next;              // the node after this group

    // 2. Reverse the group, seeding prev with groupNext so the tail links forward correctly
    ListNode prev = groupNext, cur = groupPrev.next;
    while (cur != groupNext) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }

    // 3. Reconnect
    ListNode newGroupPrev = groupPrev.next;     // the old head is now this group's TAIL
    groupPrev.next = kth;                       // link the previous group to the new head
    groupPrev = newGroupPrev;                   // advance to the new tail
}
return dummy.next;

The clever bit: prev = groupNext instead of null. Standard reversal ends with the group's tail pointing at null. Seeding prev with groupNext makes the tail point at the rest of the list automatically — stitching happens for free instead of needing a separate fix-up.

Merging

ListNode dummy = new ListNode();
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;      // attach the entire remainder at once
return dummy.next;

The last line matters. You never need to walk the leftover list node by node — it's already sorted and already terminated, so one pointer assignment attaches all of it.

Merge K Sorted Lists — two approaches

A. Min-heap of the current head of each list — O(N log k):

PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode l : lists) if (l != null) pq.offer(l);

ListNode dummy = new ListNode(), tail = dummy;
while (!pq.isEmpty()) {
    ListNode node = pq.poll();
    tail.next = node;
    tail = node;
    if (node.next != null) pq.offer(node.next);   // refill from the SAME list
}
tail.next = null;
return dummy.next;

The heap never holds more than k nodes — one per list. Each of the N total nodes passes through once at O(log k).

B. Divide and conquer — O(N log k), O(1) extra space:

while (lists.length > 1) {
    List<ListNode> merged = new ArrayList<>();
    for (int i = 0; i < lists.length; i += 2) {
        ListNode l2 = (i + 1 < lists.length) ? lists[i + 1] : null;
        merged.add(mergeTwo(lists[i], l2));
    }
    lists = merged.toArray(new ListNode[0]);
}
return lists.length == 0 ? null : lists[0];

Pair up lists and merge, halving the count each round: log k rounds, each touching all N nodes.

Naive sequential merging (merge list 1 into the result, then list 2, …) is O(N · k), because early nodes get re-walked on every merge. Name it as the brute force and reject it.

Split, reverse, merge (Reorder List)

1→2→3→4→5 becomes 1→5→2→4→3.

Recognizing the decomposition is the skill: this is three primitives you already have.

// 1. Find the FIRST middle (note fast starts one ahead)
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

// 2. Sever and reverse the second half
ListNode second = slow.next;
slow.next = null;                            // CRITICAL — cut the list in two
ListNode prev = null;
while (second != null) {
    ListNode next = second.next;
    second.next = prev;
    prev = second;
    second = next;
}

// 3. Interleave the two halves
ListNode first = head;
second = prev;
while (second != null) {
    ListNode n1 = first.next, n2 = second.next;   // save BOTH before overwriting
    first.next = second;
    second.next = n1;
    first = n1;
    second = n2;
}

slow.next = null is mandatory. Without severing, the first half still points into the second half, which now points backwards — the interleave loop cycles forever.

Trace on 1→2→3→4→5:

• After step 1: slow at 3.
• After step 2: first half 1→2→3, second half reversed to 5→4.
• Step 3: 1→5, 5→2, 2→4, 4→3 → 1→5→2→4→3. ✓

Copy List With Random Pointer

Each node has next and a random pointer to any node (or null). Produce a deep copy.

The difficulty: when you copy node A and its random points to node D, D's copy may not exist yet.

Approach A — hash map, O(n) space

Do it in two passes. First create all the clones, then wire the pointers.

Map<Node, Node> map = new HashMap<>();

for (Node cur = head; cur != null; cur = cur.next) {
    map.put(cur, new Node(cur.val));                 // pass 1: create every clone
}
for (Node cur = head; cur != null; cur = cur.next) {
    map.get(cur).next   = map.get(cur.next);         // pass 2: wire them up
    map.get(cur).random = map.get(cur.random);
}
return map.get(head);

map.get(null) returns null, which is exactly what a clone's next/random should be at the tail — so the boundary case handles itself with no if.

Approach B — interleaving, O(1) space

Weave clones into the original list: A → A' → B → B' → C → C'. Then each clone's random is simply cur.random.next, since a clone always sits directly after its original. Finally unweave. Offer this as the follow-up optimization.

The same old→new map pattern is the core of Clone Graph (16).

Add Two Numbers

Digits are stored in reverse order, so 2→4→3 is the number 342. Add two such lists.

ListNode dummy = new ListNode(), tail = dummy;
int carry = 0;

while (l1 != null || l2 != null || carry != 0) {      // ALL THREE conditions
    int sum = carry;
    if (l1 != null) { sum += l1.val; l1 = l1.next; }
    if (l2 != null) { sum += l2.val; l2 = l2.next; }
    carry = sum / 10;
    tail.next = new ListNode(sum % 10);
    tail = tail.next;
}
return dummy.next;

Reverse storage is a gift, not an obstacle — it means you encounter the ones digit first, which is exactly the order you add by hand.

carry != 0 in the loop condition handles 999 + 1. Both lists are exhausted but a carry remains, needing one more node. Dropping that condition is the standard bug, and it only shows on carry-overflow test cases.

|| l2 != null, not && — the lists can differ in length.

LRU Cache

get and put both in O(1), evicting the least-recently-used item when over capacity.

Why two structures

• HashMap gives O(1) lookup by key — but no notion of ordering.
• A doubly linked list gives O(1) move-to-front and O(1) removal from the tail — but no lookup.

Combine them: the map stores key → node, and the list maintains recency order.

Why doubly linked: to evict the tail you must repoint its predecessor. In a singly linked list, finding a node's predecessor costs O(n) — which destroys the guarantee.

head (most recent)                 tail (least recent)
 [*] ⇄ [k1|v1] ⇄ [k2|v2] ⇄ [k3|v3] ⇄ [*]
sentinel                              sentinel

Dummy head and tail sentinels mean no insert or remove ever needs a null check.

class Node {
    int key, val;
    Node prev, next;
    Node(int k, int v) { key = k; val = v; }
}

private final Map<Integer, Node> map = new HashMap<>();
private final int capacity;
private final Node head = new Node(0, 0);   // most-recently-used side
private final Node tail = new Node(0, 0);   // least-recently-used side

public LRUCache(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
}

private void remove(Node n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
}

private void insertFront(Node n) {
    n.next = head.next;
    n.prev = head;
    head.next.prev = n;
    head.next = n;
}

public int get(int key) {
    Node n = map.get(key);
    if (n == null) return -1;
    remove(n);
    insertFront(n);                 // touching it makes it most recent
    return n.val;
}

public void put(int key, int value) {
    Node existing = map.get(key);
    if (existing != null) remove(existing);

    Node node = new Node(key, value);
    map.put(key, node);
    insertFront(node);

    if (map.size() > capacity) {
        Node lru = tail.prev;       // the node just before the tail sentinel
        remove(lru);
        map.remove(lru.key);        // <- the node stores its key for exactly this line
    }
}

Why each node stores its own key: on eviction you have the node and need to delete its map entry. Without the back-reference you'd have to scan the map for it — O(n), destroying the whole guarantee. Interviewers ask about this specifically.

The sentinels' payoff: remove is two lines with no null checks, because n.prev and n.next always exist.

Recognition checklist

Common bugs

1. Returning head instead of dummy.next.
2. Not saving cur.next before overwriting it in reversal.
3. Forgetting slow.next = null when splitting a list — causes infinite loops.
4. Missing carry != 0 in the addition loop.
5. Only one null check in while (fast != null && fast.next != null).
6. A singly linked list for LRU — eviction becomes O(n).
7. Comparing nodes with .equals instead of ==.

Complexity summary