MediumLinked ListTwo Pointers

Partition List

1 approach, code in every language

You are given the head of a linked list and a target value x. Rearrange the list so that every node whose value is strictly less than x appears before every node whose value is greater than or equal to x.

Within each of the two groups, the nodes must keep the same relative order they had in the original list. Return the head of the reordered list.

Example 1

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

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

The nodes less than 3 are 1, 2, 2 (in that order) and the rest are 4, 3, 5 (in that order). Concatenating the two groups preserves both orderings.

Example 2

Input: head = [2,1], x = 2

Output: [1,2]

Only the node 1 is below the threshold, so it moves ahead of the node 2, which is greater than or equal to x.

Constraints

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

Two Dummy-Headed Chains

Build a 'less than' chain and a 'greater or equal' chain separately, then stitch them together.

Loading animation…

Intuition

Trying to shuffle nodes within a single list quickly becomes error-prone. It is far cleaner to split the traversal into two independent output chains: one collecting nodes below x and one collecting nodes at or above x. Because we append nodes in the order we encounter them, each chain automatically preserves the original relative order for its group. Two dummy heads make appending trivial, since each chain always has a stable tail to hang the next node on. Once the scan is done, we join the tail of the smaller chain to the head of the larger chain and terminate the list.

Algorithm walkthrough

1Create two dummy heads, lessDummy and greaterDummy, with tails lessTail and greaterTail pointing at them.
2Walk the original list one node at a time.
3If the current node's value is less than x, append it to lessTail; otherwise append it to greaterTail, then advance that tail.
4After the walk, terminate the greater chain by setting greaterTail.next to null.
5Link the two chains by setting lessTail.next to greaterDummy.next.
6Return lessDummy.next as the head of the partitioned list.

Implementation

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less_dummy = ListNode(0)
        greater_dummy = ListNode(0)
        less_tail = less_dummy
        greater_tail = greater_dummy
        current = head
        while current:
            if current.val < x:
                less_tail.next = current
                less_tail = less_tail.next
            else:
                greater_tail.next = current
                greater_tail = greater_tail.next
            current = current.next
        greater_tail.next = None
        less_tail.next = greater_dummy.next
        return less_dummy.next

Time

O(n)

Space

O(1)

A single pass over the n nodes rewires them into two chains in place; the only extra memory is the two dummy headers.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Retether the Sensor Pods is our own problem on the technique behind Partition List: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free