Linked List

What it is

A linked list stores a sequence as nodes connected by references rather than as consecutive array positions. A singly linked node contains a value and a next reference. A doubly linked node also contains a prev reference.

The main advantage is local structural change. Given the relevant nodes, insertion, deletion, and segment splicing require only a few pointer updates. An array may need to shift many elements for the same change. However, finding those nodes still takes time: linked lists do not provide constant-time indexed access.

Most linked-list algorithms combine a linear traversal with carefully ordered pointer updates. Repeatedly searching from the head can turn a linear task into a quadratic one. Maintaining predecessor references, building output chains, or using coordinated pointers avoids those repeated searches.

Unless stated otherwise, the techniques below assume a singly linked list with no cycle.

How to recognize it

Look for these signals:

• The input consists of nodes connected by next references.
• The task changes order, removes nodes, or joins sections without copying values.
• The head may change after an operation.
• Relative order must be preserved within selected groups.
• The task asks for a midpoint, an offset from the end, or cycle detection.
• Sorting is required, but random access is unavailable.
• Extra memory is restricted, suggesting pointer rewiring instead of an array of nodes.

Distinguish node identity from node value. Exchanging two nodes changes links; exchanging their values does not. Either may produce the same value sequence, but only one may satisfy the contract.

The core technique

1. Traverse, splice, and reverse

For deletion in a singly linked list, keep a predecessor. If prev.next is the node being removed, use prev.next = prev.next.next. For insertion, connect the new node to its successor before connecting the predecessor to the new node.

A dummy head is a temporary node placed before the real head. It makes removing or replacing the first node look like every other edit. Return dummy.next, not the dummy itself.

When bypassing several nodes, locate the first retained successor and connect directly to it. Processing an equal-value run, for example, requires identifying its boundaries before deciding which nodes remain. Advance monotonically rather than searching again for each deletion.

Reversal is the foundational rewiring pattern:

def reverse(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Before each iteration, prev heads the reversed prefix and curr heads the untouched suffix. Saving nxt preserves access to that suffix.

For sublist or block operations, first identify the predecessor, first node, last node, and successor. Then perform the internal transformation and reconnect the boundaries. Reversing one half and alternating nodes from two halves uses this same decomposition. Save each chain's next node before weaving them together.

Known segment boundaries also permit constant-time splices or exchanges. Adjacent segments require different boundary updates from separated segments; capture every boundary reference before changing links.

2. Coordinate fast and slow pointers

Use two pointers when position can be discovered through relative movement rather than counting and indexing.

• Midpoint: move slow one step and fast two. When fast finishes, slow is near the middle. Initialization determines which middle is selected for an even-length list.
• Offset from the end: advance one pointer by the desired gap, then move both together. A dummy head is useful when locating the predecessor of a node to remove.
• Cycle detection: move one pointer twice as quickly as the other. Inside a cycle, their relative position changes by one step per iteration, so they eventually meet.

After a cycle-detection meeting, reset one pointer to the head and advance both one step at a time. Their next meeting is the cycle entry.

Rotation uses another related pattern: find the length and tail, reduce the rotation modulo the length, temporarily connect the tail to the head, and cut at the new boundary. Define the rotation direction before computing that cut, and always break the temporary cycle.

3. Build stable chains

When grouping nodes by a condition, maintain a head and tail for each output chain. Append nodes in their original traversal order, then concatenate the chains. This preserves relative order within each group.

def partition(head, threshold, Node):
    low = low_tail = Node(0)
    high = high_tail = Node(0)
    curr = head
    while curr is not None:
        nxt = curr.next
        curr.next = None
        if curr.val < threshold:
            low_tail.next = curr
            low_tail = curr
        else:
            high_tail.next = curr
            high_tail = curr
        curr = nxt
    low_tail.next = high.next
    return low.next

Here, Node is a constructor whose nodes initially have next = None. Detaching each node prevents stale links from accidentally connecting groups or creating a cycle. Two dummy nodes use constant auxiliary space; the original nodes are reused.

4. Merge sorted chains

Merge sort suits linked lists because merging requires only sequential access. Compare the front nodes of two sorted chains and append the smaller one. To preserve stability, choose the left chain when keys tie.

def merge(a, b, Node, key=lambda node: node.val):
    dummy = tail = Node(0)
    while a is not None and b is not None:
        if key(a) <= key(b):
            tail.next = a
            a = a.next
        else:
            tail.next = b
            b = b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

The key can be any comparable value, not just the stored value.

Top-down merge sort splits at the midpoint, recursively sorts both halves, and merges them. Break the link between halves before recursing.

Bottom-up merge sort avoids recursion. Merge adjacent runs of lengths 1, then 2, then 4, doubling until one sorted chain remains. Each pass cuts runs apart, merges them, and reconnects the output. Track output tails carefully; every pass should traverse only a linear number of nodes.

Common mistakes

• Losing the suffix: overwriting curr.next before saving it.
• Leaving stale links: failing to terminate rebuilt chains or break temporary cycles.
• Forgetting the new head: reversal, sorting, and deletion can replace it.
• Skipping after deletion: when removing prev.next, keep prev in place to inspect its new successor.
• Dereferencing missing nodes: test fast and fast.next before advancing twice.
• Breaking stability: take from the left sorted run on equal keys.
• Confusing access with edits: a constant-time splice does not imply constant-time boundary discovery.
• Ignoring small inputs: check empty lists, single nodes, two nodes, and edits touching the tail.

Complexity

• Traversal, reversal, partitioning, midpoint search, cycle detection, and rotation take O(n) time and O(1) auxiliary space.
• Insertion, deletion, or segment splicing takes O(1) time once all required boundary handles are available. Locating them may take O(n).
• Merging chains of lengths a and b takes O(a + b) time and O(1) auxiliary space.
• Merge sort takes O(n log n) time because each of logarithmically many levels or passes processes all nodes. Top-down recursion uses O(log n) stack space; bottom-up sorting uses O(1) auxiliary space.

These bounds assume constant-time key evaluation and comparison. Auxiliary space excludes the existing nodes but includes recursion stacks and any additional collections.