Partition List: Two-Pointer Split and Reconnect

Partition List is LeetCode problem 86. You are given the head of a linked list and a value x. Partition the list so that all nodes with values less than x come before all nodes with values greater than or equal to x. The original relative order of nodes within each partition must be preserved.

Example: head = [1, 4, 3, 2, 5, 2], x = 3. The result is [1, 2, 2, 4, 3, 5].

Notice that the nodes less than 3 (the values 1, 2, 2) keep their original relative order, and the nodes greater than or equal to 3 (the values 4, 3, 5) also keep theirs.

The approach: two dummy-headed lists

The key insight is to avoid rearranging nodes in place. Instead, build two separate lists as you walk through the original:

1. Less list collects every node with a value strictly less than x.
2. Greater-or-equal list collects every node with a value greater than or equal to x.

Both lists use a dummy head node. This eliminates all special-case logic for the first insertion into each list. You just append to the tail of whichever list the current node belongs to.

After you finish iterating:

• Point the tail of the less list to the head of the greater-or-equal list (skipping its dummy node).
• Set the tail of the greater-or-equal list's next to None to terminate the result.
• Return less_dummy.next, which is the real head of the partitioned list.

This works because you never create new nodes. You just rewire existing next pointers. Every node ends up in exactly one of the two lists, and the order within each list matches the order in the original.

Visual walkthrough

Let's trace through head = [1, 4, 3, 2, 5, 2] with x = 3. Watch each node get routed to the appropriate list.

The final connection is the critical step. The less list ends at 2, and the greater-or-equal list starts at 4. You set less_tail.next = geq_dummy.next to bridge them, then set geq_tail.next = None so the list terminates cleanly.

The code

Here is the Python solution:

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

def partition(head, x):
    less_dummy = ListNode(0)
    geq_dummy = ListNode(0)
    less_tail = less_dummy
    geq_tail = geq_dummy

    while head:
        if head.val < x:
            less_tail.next = head
            less_tail = less_tail.next
        else:
            geq_tail.next = head
            geq_tail = geq_tail.next
        head = head.next

    geq_tail.next = None
    less_tail.next = geq_dummy.next
    return less_dummy.next

The key details:

• Two dummy nodes mean you never need to check whether a list is empty before appending. You just set tail.next = head and advance tail.
• head.val < x is the only comparison. Nodes equal to x go to the greater-or-equal list, which matches the problem requirement.
• geq_tail.next = None is essential. Without it, the last node in the geq list might still point to a node from the less list (from the original ordering), creating a cycle.
• less_tail.next = geq_dummy.next connects the two lists. If the less list is empty, less_dummy.next already equals None, so less_tail.next = geq_dummy.next makes the geq list the entire result.

Complexity analysis

This is optimal. Every node must be examined at least once to determine which partition it belongs to. And since you rewire existing nodes rather than allocating new ones, the space is constant.

The building blocks

This problem is built from two reusable building blocks that appear across many linked list problems.

Dual-list partitioning

You split a single input into two output lists based on a condition, then reconnect them. This same idea appears whenever you need to separate elements by some predicate while preserving order. The pattern is always the same: two dummy heads, two tail pointers, one pass, then a connection step.

This building block also shows up in:

• Sort List (LeetCode 148) uses a similar split-and-merge strategy with merge sort on linked lists.
• Odd Even Linked List (LeetCode 328) partitions nodes by position (odd index vs even index) rather than value, but the two-list technique is identical.

Dummy head technique

When building a linked list node by node, create a dummy sentinel node at the start. Append new nodes after it. Return dummy.next when done. This avoids special-casing the first insertion and eliminates null-check bugs.

In this problem, you use two dummy heads instead of one. The technique scales naturally: if you needed three partitions, you would use three dummy heads.

Edge cases to watch for

• Empty list. If head is None, the while loop never runs. Both dummy nodes point to nothing. less_dummy.next returns None.
• All values less than x. Every node goes to the less list. The geq list stays empty, so geq_dummy.next is None. The less list is returned as-is.
• All values greater than or equal to x. Every node goes to the geq list. The less list stays empty, so less_dummy.next ends up pointing to geq_dummy.next, which is the geq list's head. The result is the geq list alone.
• x is larger than all values. Same as the "all less than x" case. Every node lands in the less list.
• Single node. It goes to one list or the other. The connection step still works because the empty list's dummy just passes through.

From understanding to recall

This problem has a short, clean solution. That makes it easy to read and understand in one sitting. It also makes it easy to forget. Under pressure, the details blur. Do you need one dummy node or two? Which list do you terminate first? What happens when all nodes go to one side?

The only reliable way to retain this is to type the solution from scratch, multiple times, spaced out over days and weeks. Spaced repetition handles the scheduling so you review at exactly the right intervals. After a few reps, the two-dummy pattern and the termination step become automatic.

Related posts

• Merge Two Sorted Lists - Uses the same dummy head technique to combine two sorted lists into one
• Reverse Linked List - The foundational pointer manipulation pattern for linked lists

---

Visual Learner? Explore how linked list operations work with our Linked List Interactive Visualization.