LeetCode 86 · Linked list

Partition List, explained with a picture

Sorting coaches onto two sidings.

Linked list
▶ Watch it step by step

The problem

Rearrange a linked list so all nodes less than x come before nodes ≥ x, keeping the original order within each group.

Input:  1 → 4 → 3 → 2 → 5 → 2, x = 3
Output: 1 → 2 → 2 → 4 → 3 → 5

Picture it

Picture coaches arriving at a junction with two sidings. Coaches under x go to the first siding, the rest to the second, each in arrival order. At the end, the first siding is coupled to the front of the second.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Two dummy-headed lists, then join them. O(n).

Python solution

def partition(head, x):
    small = s = Node(0)
    big = b = Node(0)
    while head:
        if head.val < x:
            s.next = head; s = s.next
        else:
            b.next = head; b = b.next
        head = head.next
    b.next = None
    s.next = big.next
    return small.next

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.