Medium

Partition List

LAB

Given a linked list encoded as an array and x, keep relative order while moving nodes with values less than x before nodes with values at least x.

EXAMPLES

Example 1

Input
{
  "head": [
    1,
    4,
    3,
    2,
    5,
    2
  ],
  "x": 3
}

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

FUNCTION SHAPE

head: intArrayx: int→intArray

SOLUTION NOTE

The key insight is to build two separate lists in a single pass through the original list, then connect them. The dummy nodes make it easy to handle edge cases, and setting greater.next = None is crucial to prevent cycles in the final list.

This pattern of "build separate lists, then connect" is useful for many partitioning or reordering problems in linked lists.

Reveal reference solution +

pythonREFERENCE

def partition(self, head: ListNode, x: int) -> ListNode:
    # Create dummy heads for two separate lists
    smaller_dummy = ListNode(0)
    greater_dummy = ListNode(0)

    # Pointers to track the current end of each list
    smaller = smaller_dummy
    greater = greater_dummy

    # Traverse the original list
    current = head
    while current:
        if current.val < x:
            # Add to smaller list
            smaller.next = current
            smaller = smaller.next
        else:
            # Add to greater/equal list
            greater.next = current
            greater = greater.next

        # Move to next node
        current = current.next

    # Connect the two lists
    greater.next = None  # Important: prevent cycles!
    smaller.next = greater_dummy.next

    return smaller_dummy.next

TimeO(n)

SpaceO(1)

Open on LeetCode ↗