Partition List

Problem

Given the head of a singly linked list and an integer x, rearrange the list so that every node with value less than x appears before every node with value greater than or equal to x.

The partition must be stable: within each of the two groups, nodes keep their original relative order.

Examples

• Input: head = [1, 4, 3, 2, 5, 2], x = 3 → Output: [1, 2, 2, 4, 3, 5] Values < 3 are 1, 2, 2 (original order kept); values >= 3 are 4, 3, 5 (original order kept).
• Input: head = [2, 1], x = 2 → Output: [1, 2] 1 < 2 moves ahead of 2, which is >= 2.
• Input: head = [5, 6, 7], x = 3 → Output: [5, 6, 7] No value is below 3, so nothing moves.

Constraints

• 0 <= n <= 200 where n is the number of nodes.
• -100 <= Node.val <= 100, -200 <= x <= 200.

The list is small, so most approaches pass. The exercise targets the O(n)-time, O(1)-extra-space pointer solution and correct stability.

Think about it first

TL;DR

Deal nodes into a “less” chain and a “greater-or-equal” chain via two dummy heads, then splice — O(n) time, O(1) space.

Approach 1 — Brute force: collect values, rebuild

Copy all values into a Python list, stably partition it (< x first, then >= x), and write the values back over the nodes.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    vals: List[int] = []
    node = head
    while node:
        vals.append(node.val)
        node = node.next
    ordered = [v for v in vals if v < x] + [v for v in vals if v >= x]
    node = head
    for v in ordered:
        node.val = v
        node = node.next
    return head

Time O(n), space O(n). With n <= 200 it passes, but it sidesteps the skill being tested (pointer manipulation) and mutates node values, which interviewers usually disallow. The O(n) auxiliary array is the cost the next approach removes.

Approach 2 — Two dummy-headed chains (optimal)

Insight: stability is automatic if you only ever append. Deal each node, in original order, onto one of two growing chains — one for < x, one for >= x — then join them. A dummy head (a throwaway node placed before the real first node) means both chains can be appended to uniformly, with no “is this the first node?” branch.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    less_dummy = ListNode()
    geq_dummy = ListNode()
    less, geq = less_dummy, geq_dummy

    node = head
    while node:
        if node.val < x:
            less.next = node
            less = node
        else:
            geq.next = node
            geq = node
        node = node.next

    geq.next = None              # sever any stale tail pointer
    less.next = geq_dummy.next   # splice the two chains
    return less_dummy.next

Walkthrough on head = [1, 4, 3, 2, 5, 2], x = 3:

Sever the geq tail (node 5 still pointed at the second 2 in the original list), then splice: 1→2→2→4→3→5. Both groups keep their original internal order.

flowchart LR
    subgraph less["less chain"]
        L0["less_dummy"] --> L1["1"] --> L2["2"] --> L3["2"]
    end
    subgraph geq["geq chain"]
        G0["geq_dummy"] --> G1["4"] --> G2["3"] --> G3["5"]
    end
    L3 -. "less.next = geq_dummy.next" .-> G1
    G3 -. "geq.next = None" .-> X["None"]

Time O(n) — one pass plus O(1) splicing. Space O(1) — two dummy nodes and two tail pointers, regardless of n.

Approach 3 — In-place removal and re-insertion (single chain)

Insight: instead of building two chains, keep one chain and maintain an insertion point: the position after the last < x node seen so far. Walk the list; whenever you meet a < x node sitting after a >= x node, unlink it and re-insert it at the insertion point. Same complexity, more delicate — worth knowing because it generalizes to “move matching nodes forward” problems.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    insert = dummy               # last node of the "< x" prefix
    while insert.next and insert.next.val < x:
        insert = insert.next     # skip an already-correct prefix
    prev = insert
    while prev and prev.next:
        node = prev.next
        if node.val < x:
            prev.next = node.next        # unlink
            node.next = insert.next      # re-insert after prefix
            insert.next = node
            insert = node
        else:
            prev = node
    return dummy.next

Walkthrough on [2, 1], x = 2: the prefix scan stops at the dummy (2 is not < 2). Scanning: node 2 is >= 2, advance; node 1 is < 2 — unlink it and insert right after the dummy. Result 1→2.

Time O(n), space O(1). Note the found nodes are inserted after the existing prefix in encounter order, which preserves stability.

Common pitfalls

• Forgetting geq.next = None: the geq tail may still point at an earlier “less” node from the original list, creating a cycle. This is the classic bug of this problem.
• Splicing to geq_dummy instead of geq_dummy.next — the dummy must never appear in the output.
• Using <= instead of <: nodes equal to x belong in the second group.
• Trying value swaps quicksort-style — it can produce a valid partition but destroys the required stable ordering.

Pattern takeaway

When a linked-list problem asks for a stable regrouping, don’t move nodes around inside one chain — deal them into k dummy-headed chains in a single pass and splice the chains at the end. Appending to a tail is inherently stable, and the dummy heads eliminate all first-node special cases. The one step to never skip: null-terminate every chain before splicing.