Partition List — Solution

Problem

Given a linked list and a pivot value x, rearrange the list so that every node with a value strictly less than x appears before every node with a value of x or greater. The relative order of nodes within each group must be preserved.

[1,4,3,2,5,2]

• Input: head = [1, 4, 3, 2, 5, 2], x = 3
• Output: [1, 2, 2, 4, 3, 5]
• Explanation: 1, 2, 2 are all < 3 and appear first; 4, 3, 5 are all ≥ 3 and appear after, each group preserving its original order.

Intuition

The problem is really asking you to split one list into two — a "less than" group and a "greater or equal" group — then join them. Because we must preserve relative order, we can't sort or swap values: we have to redirect the actual node pointers. A dummy head on each sub-list eliminates all the edge-case checks for empty lists, letting us build both groups in a single clean pass.

Solution — Two-Dummy Partition

Build two separate linked lists simultaneously: one collecting all nodes with values less than x, the other collecting the rest. After the single traversal, null-terminate the greater list and attach it to the tail of the less list.

1. Create two dummy sentinel nodes — less_dummy and greater_dummy — and tail pointers starting at each.
2. Walk the original list; for each node, append it to the appropriate tail and advance that tail.
3. After the loop, set greater_tail.next = None to cut any stale pointer left over from the original ordering.
4. Join the two lists: less_tail.next = greater_dummy.next.
5. Return less_dummy.next as the new head.

1def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
2    less_dummy = ListNode(0)
3    greater_dummy = ListNode(0)
4    less_tail = less_dummy
5    greater_tail = greater_dummy
6
7    current = head
8    while current:
9        if current.val < x:
10            less_tail.next = current
11            less_tail = current
12        else:
13            greater_tail.next = current
14            greater_tail = current
15        current = current.next  # advance before any pointer is overwritten below
16
17    greater_tail.next = None           # sever stale pointer; prevents accidental cycle
18    less_tail.next = greater_dummy.next  # stitch: less partition → greater partition
19    return less_dummy.next

Time: O(n) — every node is visited exactly once.

Space: O(1) — only four extra pointers; no new nodes are allocated.

Complexity Summary

Common Mistakes

• Forgetting greater_tail.next = None — every node still has its original next pointer after the loop. If the last node routed to the greater list isn't the original tail, its stale pointer creates an unintended cycle or wrong connection.
• Connecting to greater_dummy instead of greater_dummy.next — the dummy node is a sentinel; the actual first node of the greater partition is greater_dummy.next.
• Using <= instead of < for the partition condition — nodes equal to x must go into the greater group, not the less group. Using <= misplaces nodes with value exactly x.
• Swapping values instead of rearranging nodes — swapping node.val looks simpler but doesn't preserve relative ordering the way the problem requires when there are equal values near the pivot.
• Advancing current before saving it — doing less_tail = current; current = current.next works only because current.next is the original next (we only ever write to .next of a tail pointer, never to current.next directly). Mixing up which .next you're writing to is a subtle source of lost nodes.

Related Problems

• Merge Two Sorted Lists — the same two-dummy-head technique used to interleave two lists in sorted order
• Odd Even Linked List — identical pattern: split into two sub-lists by a criterion (index parity), then join
• Remove Linked List Elements — single-pass filtering with a dummy head; simpler version with only one output list
• Sort List — rearranging a linked list by redirecting node pointers, uses similar sub-list building in the merge step
• Reorder List — splitting and reconnecting parts of a linked list with the same dummy-head and tail-pointer mechanics