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 tiny, so almost anything passes — the point of the exercise is the O(n) time / O(1) extra-space pointer solution and getting stability right.

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

class Solution:
    def partition(self, 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 nothing “kills” it — but it dodges the skill being tested (pointer surgery) and mutates values, which interviewers usually disallow; the O(n) auxiliary array is the flaw 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

class Solution:
    def partition(self, 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 geq tail (node 5 pointed at the second 2 in the original list), splice: 1→2→2→4→3→5. Both groups kept their original internal order.

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

class Solution:
    def partition(self, 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 only ritual to never skip: null-terminate every chain before splicing.