Partition List

A linked-list partition fails in one of two ways: it loses the unread suffix, or it preserves a stale link and creates the wrong structure. The reliable model is simpler: build two stable chains, then join and terminate them.

The contract and the answer direction

Given the head of a singly linked list and a value x, rearrange the existing nodes so that:

• every node with value < x appears first,
• every node with value >= x appears after it,
• the original relative order is preserved inside both groups.

That last condition makes this a stable linked list partition. This is not sorting. The values inside either group do not need to be ordered; they only need to remain in encounter order.

The comparison is also exact:

value < x       -> less-than chain
value >= x      -> greater-or-equal chain

A node equal to x belongs to the second chain.

The answer direction is:

1. Create two dummy-headed chains.
2. Scan the input once.
3. Append each existing node to the correct chain.
4. Connect the less-than chain to the greater-or-equal chain.
5. Explicitly terminate the final tail.
6. Return the first real node.

This is a two-chain construction problem, not a Fast & Slow Pointers problem. Fast and slow pointers are useful when the structure depends on unequal traversal rates, such as finding a midpoint or detecting a cycle. Here, the central obligation is classification plus stable append.

Recognize stable two-chain partitioning

The pattern appears when three conditions are present:

1. Each item belongs to one of two groups according to a predicate.
2. Items must preserve encounter order within their group.
3. The groups must be concatenated at the end.

For this problem, the predicate is node.val < x.

A straightforward baseline is to traverse the list, store values below x in one array, store the remaining values in another, and then write the values back in group order. That approach can demonstrate the classification logic, but it uses O(n) extra storage and shifts attention away from the linked-list operation the problem is testing.

The in-place approach uses the nodes already present. Each group becomes an append-only chain:

less:    values < x, in original order
greater: values >= x, in original order

Appending is the important choice. If you repeatedly insert nodes at the front, you reverse their order. If you search for insertion points, you add unnecessary traversal. A tail pointer gives constant-time append and makes stability almost automatic.

I would assign every pointer a specific obligation:

• current owns the next unprocessed node.
• less_tail marks the end of the built less-than chain.
• greater_tail marks the end of the built greater-or-equal chain.
• less_dummy anchors the first chain.
• greater_dummy anchors the second chain.

Once the pointers have jobs, the code stops looking like pointer juggling. It becomes bookkeeping.

Derive the pointer invariant

Dummy nodes are fixed anchor nodes that simplify list construction. They are not part of the returned result. Their only job is to give each chain a stable starting point, even when that chain has no real nodes yet.

At the start:

less_dummy    -> None
greater_dummy -> None

less_tail = less_dummy
greater_tail = greater_dummy
current = head

For each iteration, follow this order:

1. Save current.next.
2. Detach current from the unread suffix.
3. Classify current.
4. Append it to the selected chain.
5. Advance the selected tail.
6. Continue with the saved successor.

The saved successor is the critical step. Once you modify current.next, the original route into the remaining list may be gone. Save it before rewiring.

The invariant after every iteration is:

The less-than chain contains exactly the processed nodes whose values are below x, in original order. The greater-or-equal chain contains exactly the other processed nodes, also in original order. Every unprocessed node remains reachable through next_node.

Detaching each node immediately makes ownership visible:

next_node = current.next
current.next = None

Now current belongs to neither old suffix nor accidental stale chain. It is a single-node piece ready to append. This is slightly more explicit than relying on a later append to overwrite its old link, and explicit pointer ownership is valuable in an interview.

Appending to the less-than chain looks like:

less_tail.next = current
less_tail = current

Appending to the greater-or-equal chain is identical except for the tail variable. The classification changes; the construction rule does not.

Join, terminate, and prove correctness

After the scan, both chains are valid, but they are still separate.

First terminate the greater-or-equal chain:

greater_tail.next = None

This line matters even if every processed node was detached earlier. It documents and enforces the final shape. Without deliberate termination, a stale link can preserve an old suffix or connect the result back into an earlier node, producing lost nodes or a cycle.

Then join the chains:

less_tail.next = greater_dummy.next

greater_dummy.next is the first real node in the greater-or-equal chain. Finally, return:

return less_dummy.next

If the less-than chain is empty, less_dummy.next is None at that moment—but the join has already assigned it to the greater chain. That is why the dummy anchor removes head-special cases.

The correctness argument has three parts:

1. Classification establishes the boundary.
   Every processed node is sent to the less-than chain exactly when node.val < x. Otherwise it goes to the greater-or-equal chain.

2. Tail appends establish stability.
   Each node is appended after all earlier nodes assigned to its group. Therefore, each chain preserves original relative order.

3. Single traversal establishes completeness and preservation.
   Each original node is processed once and attached to exactly one chain. No new data node replaces it; the output reuses the original nodes.

The dummy nodes are temporary anchors. The actual output consists of the original input nodes.

Dry-run: mixed and empty lists

Use:

input:  1 -> 4 -> 3 -> 2 -> 5 -> 2
x:      3

The strict boundary is value < 3.

Current node	Saved next	Destination	Less chain	Greater-or-equal chain
1	4	less	1	empty
4	3	greater-or-equal	1	4
3	2	greater-or-equal	1	4 -> 3
2	5	less	1 -> 2	4 -> 3
5	2	greater-or-equal	1 -> 2	4 -> 3 -> 5
2	None	less	1 -> 2 -> 2	4 -> 3 -> 5

Notice two details:

• The two values 2 remain in their original order.
• The value 3 goes to the second chain because the condition is < 3, not <= 3.

After the scan:

less:    1 -> 2 -> 2
greater: 4 -> 3 -> 5

Terminate the greater chain, connect the less tail to the greater head, and obtain:

1 -> 2 -> 2 -> 4 -> 3 -> 5

The input can also be empty:

head = None

The loop does not run. Both real chains remain empty, greater_tail.next is set to None, less_tail.next points to greater_dummy.next, and the returned head is None.

That is the useful property of dummy nodes: the empty case follows the same control flow as every other case.

Python implementation

The following implementation assumes the usual ListNode shape with .val and .next fields.

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next


class Solution:
    def partition(
        self,
        head: Optional[ListNode],
        x: int,
    ) -> Optional[ListNode]:
        less_dummy = ListNode()
        greater_dummy = ListNode()

        less_tail = less_dummy
        greater_tail = greater_dummy
        current = head

        while current is not None:
            next_node = current.next
            current.next = None

            if current.val < x:
                less_tail.next = current
                less_tail = current
            else:
                greater_tail.next = current
                greater_tail = current

            current = next_node

        greater_tail.next = None
        less_tail.next = greater_dummy.next

        return less_dummy.next

Read the loop as a direct translation of the invariant:

next_node = current.next

Preserve access to the unread suffix before changing any link.

current.next = None

Make the current node an isolated piece. This prevents an old successor from silently becoming part of the wrong chain.

if current.val < x:

Apply the strict boundary. Equality takes the else branch.

less_tail.next = current
less_tail = current

Append to the correct chain, then move its tail to the newly appended node.

current = next_node

Resume from the node that was saved before rewiring.

The two lines after the loop are not cleanup that can be omitted:

greater_tail.next = None
less_tail.next = greater_dummy.next

The first defines the final endpoint. The second performs the final concatenation.

A common alternative leaves current.next attached during the loop and overwrites links as it appends. That can work, but it requires more mental tracking of which old links will eventually be replaced. In an interview, I prefer the explicit detach because it makes node ownership and termination easier to inspect.

Complexity and submission checks

Let n be the number of nodes.

• Time: O(n). Each node is inspected once, classified once, and appended with constant-time pointer updates.
• Auxiliary space: O(1). The algorithm uses a fixed number of pointers and two fixed dummy nodes. It does not allocate replacement nodes or arrays proportional to n.

Before submitting, test the cases that expose pointer mistakes:

• Empty list.
• Singleton list.
• Every node less than x.
• Every node greater than or equal to x.
• x below every value.
• x above every value.
• Several values equal to x.
• Already partitioned input.
• Alternating input such as less, greater, less, greater.

Equality-heavy inputs are especially useful. They verify that you did not accidentally write <= x and move equal values into the wrong chain.

Also inspect the final pointer, not just the visible values. A result that prints correctly for a short example may still contain a cycle or an unreachable suffix. The final greater-or-equal tail must point to None.

The transferable pattern

When a linked-list problem asks for stable classification into groups, do not repeatedly move nodes through the existing structure. Build append-only chains instead.

The reasoning sequence is:

1. Name the classification predicate.
2. Give each group a dummy anchor and tail.
3. Save the unprocessed successor before rewiring.
4. Append the current node to exactly one chain.
5. Join the chains.
6. Terminate the final tail deliberately.

The durable rule is simple:

Own the unread suffix, preserve order by appending, and make the final None explicit.

That is the heart of a reliable Partition List solution—and a reusable way to approach many in-place linked-list problems.