LeetCode 86: Partition List

Problem Restatement

We are given the head of a linked list and an integer x.

We need to reorder the list so that:

nodes with value < x

come before:

nodes with value >= x

The relative order inside each group must stay the same.

The official statement says to partition the list around x, preserving the original relative order of nodes in both partitions. The constraints allow 0 to 200 nodes, node values from -100 to 100, and x from -200 to 200.

Input and Output

Function shape:

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

Examples

Example 1:

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

Nodes less than 3 are:

1, 2, 2

Nodes greater than or equal to 3 are:

4, 3, 5

Preserve the original order in both groups.

Answer:

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

Example 2:

head = [2, 1]
x = 2

Nodes less than 2:

1

Nodes greater than or equal to 2:

2

Answer:

[1, 2]

First Thought: Collect Values in Arrays

A simple method is to scan the linked list and put values into two arrays.

small = []
large = []

For each node:

if node.val < x:
    small.append(node.val)
else:
    large.append(node.val)

Then build a new linked list from:

small + large

This preserves order, but it creates new storage for values and new nodes.

We can solve the problem by rearranging the existing nodes directly.

Key Insight

We need two ordered groups:

1. Nodes with value < x
2. Nodes with value >= x

A clean way to build them is to maintain two separate linked lists while scanning the original list.

Use two dummy heads:

less_dummy
greater_dummy

and two tails:

less_tail
greater_tail

When we see a node with value < x, append it to the less list.

Otherwise, append it to the greater list.

At the end, connect:

less_tail.next = greater_dummy.next

Then terminate the greater list:

greater_tail.next = None

The termination is important. The original nodes still have their old next pointers. Without cutting the final pointer, the result can accidentally keep stale links or form an incorrect chain.

Algorithm

Create two dummy nodes:

less_dummy = ListNode(0)
greater_dummy = ListNode(0)

Create two tail pointers:

less_tail = less_dummy
greater_tail = greater_dummy

Scan the original list using cur.

For each node:

1. Save the next node.
2. If cur.val < x, append cur to the less list.
3. Otherwise, append cur to the greater list.
4. Move to the saved next node.

After the scan:

1. Set greater_tail.next = None.
2. Set less_tail.next = greater_dummy.next.
3. Return less_dummy.next.

Walkthrough

Use:

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

Start with two empty lists:

less:    dummy
greater: dummy

Read 1.

Since 1 < 3, append it to less:

less:    1
greater:

Read 4.

Since 4 >= 3, append it to greater:

less:    1
greater: 4

Read 3.

Since 3 >= 3, append it to greater:

less:    1
greater: 4 -> 3

Read 2.

Since 2 < 3, append it to less:

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

Read 5.

Since 5 >= 3, append it to greater:

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

Read final 2.

Since 2 < 3, append it to less:

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

Connect the two lists:

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

Correctness

The algorithm scans the original list from left to right.

Whenever it sees a node with value < x, it appends that node to the end of the less list. Since nodes are appended in scan order, the less list preserves the original relative order of all nodes with value < x.

Whenever it sees a node with value >= x, it appends that node to the end of the greater list. Since nodes are appended in scan order, the greater list preserves the original relative order of all nodes with value >= x.

Every original node is appended to exactly one of the two lists, because every value either satisfies val < x or val >= x.

After the scan, connecting the tail of the less list to the head of the greater list places all smaller nodes before all greater-or-equal nodes. Since each partition already preserves its own order, the final list satisfies all requirements.

Therefore, the algorithm returns the correct partitioned list.

Complexity

Let:

n = number of nodes

The output reuses the original linked list nodes.

Implementation

# 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(0)
        greater_dummy = ListNode(0)

        less_tail = less_dummy
        greater_tail = greater_dummy

        cur = head

        while cur:
            nxt = cur.next

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

            cur = nxt

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

        return less_dummy.next

Code Explanation

Create two dummy heads:

less_dummy = ListNode(0)
greater_dummy = ListNode(0)

The dummy nodes simplify appending. We do not need special logic for the first node in either list.

Create tails:

less_tail = less_dummy
greater_tail = greater_dummy

Scan the original list:

cur = head

Before rewiring a node, save its original next pointer:

nxt = cur.next

If the current node belongs in the less partition:

if cur.val < x:
    less_tail.next = cur
    less_tail = less_tail.next

Otherwise, append it to the greater partition:

else:
    greater_tail.next = cur
    greater_tail = greater_tail.next

Move forward using the saved pointer:

cur = nxt

After all nodes are distributed, terminate the greater list:

greater_tail.next = None

Then connect the two partitions:

less_tail.next = greater_dummy.next

Return the real head:

return less_dummy.next

Testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values

def check(values, x, expected):
    s = Solution()
    head = build_list(values)
    result = s.partition(head, x)
    assert to_list(result) == expected

def run_tests():
    check([1, 4, 3, 2, 5, 2], 3, [1, 2, 2, 4, 3, 5])
    check([2, 1], 2, [1, 2])
    check([], 3, [])
    check([1], 2, [1])
    check([3], 2, [3])
    check([1, 2, 2], 3, [1, 2, 2])
    check([4, 5, 6], 3, [4, 5, 6])
    check([3, 1, 2, 3, 0], 3, [1, 2, 0, 3, 3])

    print("all tests passed")

run_tests()

Test meaning: