Linked lists

You’ll recognise it when

• The input is a ListNode (or Node) with a next field, not an array.
• You must rewire nodes rather than copy them: reverse, reorder, merge, delete.
• The task says in place or O(1) extra memory, so dumping the values into an array is off the table.
• You need a position you can’t index directly: the middle, the k-th from the end, where a cycle starts.

Fast and slow pointers on a list are a cousin of two pointers on an array: both walk a sequence with two positions, but on a list you can only ever move forward.

The idea

Picture a line of people, each with a hand on the shoulder of the person in front. To make the line face the other way, you walk down it and ask each person to put their hand on the person behind them instead. The catch: the moment someone lets go of the shoulder in front, nobody in your part of the line is touching the rest of it any more. So before anyone lets go, you point at the person in front so you don’t lose them.

That’s the whole algorithm. A singly linked list only knows “next”. To reverse it you turn every next arrow around, one node at a time, and you need three fingers to do it without dropping anything: one on the node behind (prev), one on the node you’re turning (curr), and one saving the rest of the list (nxt).

How it works

prev starts at None (the reversed part is empty) and curr at the head. Scroll through the steps and the graphic follows along; press play, or edit the list and try one or two nodes.

Why it’s correct: at the top of every loop, following arrows from prev gives the nodes already visited in reverse order, and following from curr gives the untouched nodes in their original order. One pass moves exactly one node from the second list to the front of the first, so when the second list is empty, prev holds the whole list reversed.

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


def reverse(head):
    """Reverse a singly linked list in place and return the new head."""
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

struct Node {
    int val;
    Node* next;
    Node(int val, Node* next = nullptr) : val(val), next(next) {}
};

// Reverse a singly linked list in place and return the new head.
Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    while (curr) {
        Node* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

class Node {
    int val;
    Node next;

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

class LinkedList {
    // Reverse a singly linked list in place and return the new head.
    static Node reverse(Node head) {
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node nxt = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nxt;
        }
        return prev;
    }
}

Why it’s O(n)

The loop runs once per node, and each pass does three pointer assignments. That’s O(n) time for n nodes. The only extra memory is three pointers, whatever the length, so space is O(1).

Common mistakes

curr.next = prev; curr = curr.next        # ✗ curr.next is prev now: walks backwards
nxt = curr.next; curr.next = prev; curr = nxt  # ✓ save first, then rewire

return head   # ✗ the old head is now the last node
return prev   # ✓ the old tail, now first

curr = nxt; prev = curr   # ✗ prev skips ahead to nxt
prev = curr; curr = nxt   # ✓ prev takes the node we just turned

Variations

• Reverse between positions left and right. Walk to the node just before left, reverse the next right - left + 1 nodes with the same three-pointer loop, then reconnect both ends. Put a dummy head in front first, so left = 1 needs no special case.
• Merge two sorted lists (dummy head). Make dummy = Node(0) and a tail pointer at it. Repeatedly attach the smaller of the two front nodes to tail.next and move tail on; when one list runs out, attach the rest of the other in one step. Return dummy.next. The dummy means the first node is handled like every other. For k lists, pick the smallest front with a heap.
• Remove the n-th node from the end. Start two pointers at a dummy head and move fast n steps ahead. Then move both until fast is on the last node: slow is now just before the node to remove, so slow.next = slow.next.next. Thanks to the dummy, removing the head works too.
• Find the middle. slow moves one step and fast two, while fast and fast.next. When fast runs out, slow is on the middle (the second of the two middles on an even-length list). This is the first move of “reorder list” and “is it a palindrome”: find the middle, reverse the second half, compare or interleave.
• Detect a cycle (Floyd). The same slow and fast. If fast reaches None there’s no cycle. If there is one, both end up inside it and fast gains one node per step, so they meet within one lap: O(n) time, O(1) space. To find where the cycle starts, move one pointer back to the head and step both by one; they meet at the cycle’s first node.