Linked lists

The linked list coding pattern for interviews. A dummy head, fast and slow pointers, reversing in place and merging, with a step-through, templates in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Foundation13 min read

Read first: Two pointers

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node, and nothing else. You can’t jump to the fifth node. You have to walk there from the head, the first node. That one limit shapes every linked list problem.

The good news is that the problems use only a few moves. Walk with one pointer. Walk with two pointers at different speeds. Flip a pointer to reverse the list. Splice nodes from two lists into one. The algorithms are short. The bugs come from losing a node: you change a pointer before you saved where it led, and the rest of the list is gone. So the real skill is knowing, at every line, which pointers you still need.

How to spot it

The input is a ListNode. Then these moves are your toolbox, and you rarely need anything else.
“In place” or “O(1) extra memory” on a list. Copying the n values into an array is easy, but it uses O(n) memory and is usually not the answer wanted.
The middle, the kth node from the end, or a loop. Two pointers with a gap or a speed difference find these in one pass.
Reorder, rotate, swap pairs or reverse a part. These are cut, reverse and reconnect steps.
Merge sorted lists. Two lists use the merge loop. With k lists, add a heap.

A list is also hiding inside other problems. An LRU cache uses a doubly linked list, where each node also points back to the one before it. That gives O(1) removal from the middle.

Watch it run

Reverse the list 1 → 2 → 3 → 4 → 5. Watch the arrow between the reversed part and the rest. When node 1’s arrow flips, nothing points from node 1 to node 2 anymore. Only next_node still knows where node 2 is. Saving it first is the whole trick.

reversed part

empty

still to do

12345

previous, current = None, head
while current:
next_node = current.next # save the rest
current.next = previous # flip one arrow
previous, current = current, next_node
return previous # the new head

Each node knows only the node after it. Reverse the list without a second list: flip the arrows one at a time.

1 / 12

At every step the list is cut into two clean chains. previous is the head of the reversed part, and current is the head of the part still to do. Each step moves one node from the second chain to the first. That’s the invariant to say out loud, and it also tells you the answer at the end. When the second chain is empty, previous is the whole reversed list.

The template

Reverse in place, merge two sorted lists with a dummy head, and find the middle with fast and slow pointers:

LinkedLists.javalist_node.pyLinkedLists.cslist_node.golist-node.ts

import java.util.ArrayList;
import java.util.List;

public class LinkedLists {
    static ListNode reverseList(ListNode head) {
        // Reverse in place. Flipping current.next cuts us off from the rest of the list, so we save
        // it in next first. previous is always the head of the part already reversed. O(n) time,
        // O(1) memory.
        ListNode previous = null, current = head;
        while (current != null) {
            ListNode next = current.next; // save the rest before the link to it is lost
            current.next = previous; // flip one arrow
            previous = current;
            current = next;
        }
        return previous; // the old tail is the new head
    }

    static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // Merge two sorted lists. The dummy node gives the result a head before we know which list
        // wins the first place, so there's no special case for the first node. O(n + m) for lists
        // of n and m nodes.
        ListNode dummy = new ListNode(0), tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) { // <= keeps equal values in their original order
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        // What is left is already sorted, so link it whole.
        tail.next = list1 != null ? list1 : list2;
        return dummy.next;
    }

    static ListNode middleNode(ListNode head) {
        // Fast moves two steps for each one slow moves, so when fast runs out, slow is halfway.
        // One pass and O(1) memory, without counting the length first.
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow; // for an even length, the second of the two middles
    }

    public static void main(String[] args) {
        check(values(reverseList(build(1, 2, 3, 4, 5))).equals(List.of(5, 4, 3, 2, 1)));
        check(reverseList(null) == null);
        check(values(mergeTwoLists(build(1, 4, 6), build(2, 3, 7, 9)))
                .equals(List.of(1, 2, 3, 4, 6, 7, 9)));
        check(values(mergeTwoLists(null, build(5))).equals(List.of(5)));
        check(middleNode(build(1, 2, 3, 4, 5)).val == 3);
        check(middleNode(build(1, 2, 3, 4)).val == 3);
        System.out.println("ok: reverseList, mergeTwoLists and middleNode");
    }

    static ListNode build(int... numbers) {
        ListNode dummy = new ListNode(0), tail = dummy;
        for (int number : numbers) {
            tail.next = new ListNode(number);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> values(ListNode node) {
        List<Integer> result = new ArrayList<>();
        for (; node != null; node = node.next) result.add(node.val);
        return result;
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Look at the loop conditions. Reverse runs while current, because every node must flip. Middle runs while fast and fast.next, because fast reads two nodes ahead and needs both. Get one of these wrong and you either skip the last node or read a pointer that is null.

Variations

Remove the nth node from the end

Move a lead pointer n steps ahead (n is position_from_end in code). Then move lead and a trail pointer together until lead reaches the last node. The gap between them stays n, so trail stops just before the node to remove. Start both at a dummy head. Then removing the real head is not a special case.

Reorder and palindrome checks

Reorder List turns 1 → 2 → 3 → 4 → 5 into 1 → 5 → 2 → 4 → 3. It’s three moves from this page in a row. Find the middle with fast and slow. Reverse the second half. Then weave the two halves together, one node from each. Palindrome Linked List uses the same first two moves, then compares the halves node by node. Both run in O(n) time and O(1) memory.

Reverse a part of the list

To reverse nodes from position left to right, walk to the node just before left and keep it. Reverse the next right - left + 1 nodes with the usual loop. Then connect both ends back. The node before the part points to the new start, and the old start points to what came after. The k-group version repeats this for every block of k nodes.

Cycles

Fast and slow meet inside a loop if there is one. This is explained on the two pointers page. To find where the loop starts, move one pointer back to the head after they meet. Then move both one step at a time. They meet again at the start of the loop.

Complexity

	Time	Extra memory
Reach the kth node	O(k)	O(1)
Reverse, find middle, find loop	O(n)	O(1)
Merge two sorted lists	O(n + m)	O(1)
Reverse recursively	O(n)	O(n) stack
Merge k lists with a heap	O(N log k)	O(k)

Say this out loud

I’ll keep two chains: previous is the reversed part, and current is what’s left. Each step I save current.next, point current back at previous, and move both forward. Every node moves once, so it’s O(n) time and O(1) memory.

Interview questions

Interviewer asksWhy use a dummy node? Couldn't you just handle the head separately?

You can, but it takes an extra branch for “the result is empty so far”. That branch is where bugs hide. With a dummy node, the tail always exists, so every node is added the same way. It costs one extra node. Return dummy.next, never dummy.

Interviewer asksCan you reverse the list recursively? What does it cost?

Yes. Reverse everything after the head, then make the old second node point back at the head, and set the head’s next to null. It is O(n) time, but the call stack holds n frames. That’s O(n) memory, and a very long list can overflow the stack. The loop version is safer.

Interviewer asksFor an even length list, which middle does fast and slow return?

With while fast and fast.next, slow stops on the second of the two middles. For 1, 2, 3, 4 it returns 3. To get the first middle, start fast one step ahead, at head.next. Pick the one your next step needs. Reorder List splits after the first middle, so the first half is not shorter than the second.

Practice

10 problems on LeetCode: 4 easy, 5 medium, 1 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Four of these are solved step by step on this site, as part of the Blind 75: Reverse Linked List, Merge Two Sorted Lists, Remove Nth Node From End of List and Reorder List. Two more use the same moves: Linked List Cycle and Merge k Sorted Lists.

Recap

Use it when the input is a linked list and you must work in place, find a middle, find a loop, reorder or merge.
Four moves: dummy head, fast and slow, reverse in place, merge.
The rule: save a pointer before you overwrite the link to it.
Cost: O(n) time and O(1) memory for almost everything. Recursion adds O(n) stack.
Watch for: losing the rest of the list, null checks in while fast and fast.next, and returning the dummy instead of dummy.next.