Linked list

A linked list is a chain of nodes. Each node holds a value and a reference (a link) to the next node; the last node links to nothing, written null. You only hold the first node, the head. There is no index: to reach the tenth node you walk nine links. In exchange, adding or removing a node next to one you already hold takes constant time, because only links change and nothing has to shift.

Interviewers like linked lists because the code is short but easy to break: one link changed in the wrong order loses the rest of the list. Almost every problem uses four moves.

Move 1: walk the list

Start at the head and follow next until you reach the end. Check for the empty list (no head at all) before you read anything from a node. Most crashes in linked list code come from reading next on a node that does not exist.

Move 2: a placeholder node in front

When the head itself might change (removing the first node, merging two lists, reversing in groups), create a placeholder node whose next is the head. Work from the placeholder and return placeholder.next at the end. The first node then behaves like every other node, and the special cases disappear.

Move 3: turn links around

Reversing needs three references: the part already reversed (previous), the node you are working on (current), and the rest of the list. The order of the steps matters: save the rest first, then point the current node backwards, then step both references forward. The picture shows it on 1, 2, 3.

If you change the link before saving the rest, the rest of the list is lost: after step 1 above, nothing points to node 2 any more except the saved reference.

Move 4: a slow and a fast pointer

(A pointer is the same thing as a reference.) Move one reference one node per step and another two nodes per step. When the fast one reaches the end, the slow one is in the middle: for 1 to 5, slow visits 1, 2, 3 while fast visits 1, 3, 5. The same pair detects a loop: inside a loop the fast pointer gains one node per step, so the two must meet. Putting one pointer back at the start and moving both one step at a time then finds where the loop begins (Floyd's method). Two pointers kept n nodes apart find the nth node from the end in one pass.

public class Main {
    static class Node {
        int val;
        Node next;

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

    static Node build(int... values) {
        Node head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new Node(values[i], head);
        }
        return head;
    }

    static Node middle(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    static Node reverse(Node head) {
        Node previous = null;
        Node current = head;
        while (current != null) {
            Node next = current.next;   // 1. remember the rest
            current.next = previous;    // 2. turn the link around
            previous = current;         // 3. step forward
            current = next;
        }
        return previous;
    }

    static String show(Node head) {
        StringBuilder text = new StringBuilder();
        for (Node n = head; n != null; n = n.next) {
            text.append(n.val).append(n.next != null ? " -> " : "");
        }
        return text.toString();
    }

    public static void main(String[] args) {
        Node head = build(1, 2, 3, 4, 5);
        System.out.println("middle: " + middle(head).val);
        System.out.println(show(reverse(head)));
    }
}

middle: 3
5 -> 4 -> 3 -> 2 -> 1

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


def build(*values):
    head = None
    for v in reversed(values):
        head = Node(v, head)
    return head


def middle(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    return slow


def reverse(head):
    previous, current = None, head
    while current is not None:
        following = current.next    # 1. remember the rest
        current.next = previous     # 2. turn the link around
        previous = current          # 3. step forward
        current = following
    return previous


def show(head):
    values = []
    while head is not None:
        values.append(str(head.val))
        head = head.next
    return " -> ".join(values)


head = build(1, 2, 3, 4, 5)
print("middle:", middle(head).val)
print(show(reverse(head)))

middle: 3
5 -> 4 -> 3 -> 2 -> 1

Combining the moves

Harder problems join these moves. A palindrome check (does the list read the same forwards and backwards?) finds the middle (move 4), reverses the second half (move 3), and compares the halves. Reversing in groups of k uses a placeholder (move 2) and the reversal loop (move 3) on each group. Adding two numbers stored digit by digit walks both lists together (move 1) and builds the result after a placeholder.

How to answer in an interview

Draw the nodes and arrows, on paper or in words, before you code. Name the references you will keep and say the order of the link changes out loud. Then run your code by hand on an empty list, one node and two nodes. Finish with the cost: these moves visit each node a constant number of times, so O(n) time and O(1) extra space.

Common mistakes

• Reading next from a null node, often at the end of a loop or on an empty list.
• Changing a link before saving the node it pointed to.
• Special-casing the head by hand instead of using a placeholder, and getting it wrong.
• Checking only fast.next without checking fast first, which crashes on even lengths.
• Copying the values into an array first: it works, but uses O(n) extra space, and interviewers usually ask you to avoid it.

Recap

Walk carefully, put a placeholder in front when the head may change, save the rest before turning a link, and use slow and fast pointers for the middle, loops and "nth from the end". Test the empty list, one node and two nodes every time.