Linked lists

A reversal that keeps one node

A payment service tells merchants about every payment by calling their webhook. When a merchant's server is down, the calls wait in an in-memory list, newest first. A change makes the worker deliver the oldest first, by reversing the list before each run. It passes review. The test list has one webhook in it.

Then a large merchant comes back from an outage with 5,000 webhooks waiting. The worker delivers one, and the list is empty. 4,999 payment notices are gone, and the merchant's paid orders show as unpaid.

Here is the reversal that shipped. Run it in your head on three nodes, 1 → 2 → 3, before reading on.

Pause and predict The line cur.next = prev overwrites cur.next. Which value must the loop save in a variable before that line runs, so the reversal works?

The rest of the list hangs from one pointer

A node in a singly linked list stores a value and one pointer, next, to the node after it. The list has no index you can jump to, no stored length, and no pointer back to the previous node.

So if you overwrite the only pointer to a node, you can no longer reach that node or anything after it. Every technique in this unit is a way of changing pointers without losing a node like that.

Take reversing a list in place. Two handles split the nodes into two chains. prev points to the first node of the part already reversed, and cur points to the first node of the part not yet touched. Each step moves one node from the front of the untouched chain to the front of the reversed chain.

A dummy head

To remove or insert a node, you change the next pointer of the node before it. The head has no node before it, so code that changes the front of the list needs a separate case, and that separate case is where bugs tend to appear.

A dummy head is an extra node, holding no real value, that you place before the real head. Now every real node has a node before it, so the same code handles all of them. When you build a new list, keep a pointer called tail on its last node, starting at the dummy, and attach each new node after tail.

Pause and predict You built a merged list by attaching nodes after a dummy node. Which pointer do you return as the head of the result?

Two speeds: Floyd

Suppose you need to know whether a list loops back on itself, meaning some node's next points to an earlier node. A set of visited nodes answers this with O(n) extra memory. Fast and slow pointers answer it with O(1): both start at the head, and on each step slow moves one node and fast moves two.

Pause and predict Both pointers are now inside the loop, and going forward round the loop, fast is some number of nodes behind slow. How does that distance change with each step?

Finding the node where the loop starts takes one more step. Call the part of the list before the loop the tail, and say it is a nodes long. Say the loop has c nodes, and the two pointers meet b steps past the loop's first node.

Check it on 7, 3, 9, 4, 8, 1 with the last node pointing back to 9. The tail is 7, 3, so a = 2, and the loop is 9, 4, 8, 1, so c = 4. The pointers meet at 8 after t = 4 steps, which is b = 2 nodes past 9, and indeed a = 2 = 1 × 4 - 2. After two more steps each, p and slow meet at 9.

A gap of n

To find "the n-th node from the end" you would normally need the list's length, which you do not have. You could walk the list once to count the nodes and a second time to stop at the right one. You can also do it in one pass. Put a dummy before the head and start two pointers on it. Move the first pointer, the leader, n nodes ahead. Then move both pointers one node at a time until the leader is on the last node. The two pointers stay n nodes apart the whole time, so the trailing pointer stops on the node just before the target. That is the node whose next you change to remove the target.

The same rewiring, on a doubly linked list next to a hash map, is how a cache keeps its least recently used key ready to evict: System design: inside a cache.

How to recognise it

These problems give you a linked list and ask about its shape: reverse it, reorder it, find out whether it loops, find its middle, or find a node counted from the end. The constraint that usually decides the method is "O(1) extra space" or "in place".

Pause and predict You must remove the 3rd node from the end of a list, walking the list only once. Which technique fits?

The ones that only look like it

• Two pointers on an array: on an array you can start at both ends and jump to any index, including the middle. A list allows none of that, so you reach its middle with fast and slow pointers and its far end by reversing it. See two pointers for the array version.
• Merging k sorted lists: the dummy and the tail pointer work the same way, but choosing the smallest of the k front nodes at each step needs a heap.
• Finding a repeated node when memory is not limited: a hash set of visited nodes is a fine first answer. Use Floyd's fast and slow pointers when the interviewer asks for O(1) extra space.

Where it bites

• Rewiring before saving. Running cur.next = prev before saving cur.next loses the rest of the list. Save the next node first, then rewire, then advance.
• Not cutting after a split. In Reorder List, if the last node of the first half still points into the second half, weaving the halves together creates a loop. Set the middle node's next to null when you split.
• Returning the wrong pointer. After a reversal, return prev: cur is null, and head now points to the last node. When you built the list after a dummy, return dummy.next.
• Null checks in the wrong order. Write fast != null && fast.next != null in that order. If the code reads fast.next first while fast is null, the check itself crashes.
• Comparing values instead of nodes. Two different nodes can hold the same value. When you check whether two pointers have met, compare the nodes themselves (== in Java, is in Python), not their values.
• Reversing a short last group in k-groups. If fewer than k nodes are left at the end, they must stay in order. Count k nodes ahead before you change any pointer in a group.

Pause and predict In Python, someone writes the loop body as the single line prev, cur, cur.next = cur, cur.next, prev. What happens when it runs on the list 1, 2, 3?