Partition List — Two Dummy Head Chains for Stable Partitioning

Problem Statement#

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Constraints:

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

Example 1:

Input:  head = [1, 4, 3, 2, 5, 2], x = 3
Output: [1, 2, 2, 4, 3, 5]
Explanation: Nodes with val < 3: [1,2,2]. Nodes with val >= 3: [4,3,5]. Relative order preserved.

Example 2:

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

Example 3:

Input:  head = [], x = 0
Output: []

Why This Problem Matters#

Partition List (LeetCode 86) is the value-based version of Odd Even Linked List — instead of grouping by index parity, you group by value comparison against a pivot. Bloomberg and Amazon ask this problem because it tests the two-chain (dual dummy head) pattern combined with the partition concept from Quicksort.

The "stable" requirement is the key constraint that separates this from a naive approach. A naive approach might use sorting or multiple passes, but stability (preserving relative order within each partition) means you must maintain the original traversal order for each group. The two-chain technique inherently preserves order because you add nodes to each chain in the order you encounter them.

This pattern is the foundation for partition-based linked list sorting. In linked list Quicksort, you'd partition around a pivot (like this problem), then recursively sort each partition. Understanding the stable two-chain partition is thus foundational for understanding sorting on linked lists.

The critical edge case that trips up many candidates: if you don't terminate the greater chain with None before connecting it, the last greater node still points to some earlier node — creating a cycle. This is the most common bug in this problem.

The Core Insight#

Create two dummy heads: less_dummy and greater_dummy. Traverse the original list with a single pointer. For each node, if node.val < x, append it to the less chain; otherwise, append it to the greater chain.

After the traversal:

1. Terminate the greater chain: greater.next = None — this prevents cycles from the last greater node still pointing to an old next.
2. Connect the less chain tail to the head of the greater chain: less.next = greater_dummy.next
3. Return less_dummy.next

The two dummy nodes ensure both chains are uniformly built without special-casing the chain head initialization.

Visual Dry Run#

Input: 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3

After traversal:

• Less chain: 1 -> 2 -> 2 (tail less points to node 2, last in less chain)
• Greater chain: 4 -> 3 -> 5 (tail greater points to node 5, but node 5 still has .next from original list!)

Critical step: greater.next = None — node 5's next was None in the original (it was the last node), but if it weren't, this step would prevent a cycle.

Connect: less.next = greater_dummy.next = node 4.

Result: 1 -> 2 -> 2 -> 4 -> 3 -> 5

Solution (Optimal)#

Python#

def partition(head, x):
    # Two dummy heads for two chains
    less_dummy = ListNode(0)
    greater_dummy = ListNode(0)
 
    less = less_dummy        # tail of less-than chain
    greater = greater_dummy  # tail of greater-or-equal chain
 
    curr = head
    while curr:
        if curr.val < x:
            less.next = curr   # append to less chain
            less = less.next
        else:
            greater.next = curr  # append to greater chain
            greater = greater.next
        curr = curr.next
 
    # CRITICAL: terminate greater chain to prevent cycles
    greater.next = None
 
    # Connect less chain to greater chain
    less.next = greater_dummy.next
 
    return less_dummy.next

Time complexity: O(n) — single pass.

Space complexity: O(1) — two dummy nodes and pointer variables.

JavaScript#

var partition = function(head, x) {
    const lessDummy = new ListNode(0);
    const greaterDummy = new ListNode(0);
 
    let less = lessDummy;
    let greater = greaterDummy;
    let curr = head;
 
    while (curr !== null) {
        if (curr.val < x) {
            less.next = curr;
            less = less.next;
        } else {
            greater.next = curr;
            greater = greater.next;
        }
        curr = curr.next;
    }
 
    // Terminate greater chain — prevents cycles
    greater.next = null;
 
    // Connect chains
    less.next = greaterDummy.next;
 
    return lessDummy.next;
};

Complexity:

Common Mistakes#

1. Forgetting greater.next = None. This is the most dangerous bug. The last node appended to the greater chain still has its original .next pointer from the input list. If that points to an earlier node, you've created a cycle. If it points to a node that ended up in the less chain, you've created a fork. Always terminate the greater chain.

2. Using curr.val <= x instead of curr.val < x. The problem says "less than x" goes to the first partition, "greater than or equal to x" goes to the second. Using <= puts equal-to-x values in the less chain incorrectly.

3. Forgetting curr = curr.next in the loop. You're iterating over the original list via curr. Don't confuse advancing curr with advancing less or greater. All three advance independently.

4. Not handling empty list. If head = None, curr is None, the while loop doesn't execute, greater.next = None is applied to greater_dummy.next = None (already none), less.next = greater_dummy.next = None. Returns less_dummy.next = None. Correct and automatic.

5. Connecting chains in the wrong order. Connect less.next = greater_dummy.next (not less.next = greater). greater is the tail of the greater chain, not the head. greater_dummy.next is the head of the greater chain.

Interview Tips#

1. Name the two dummy nodes explicitly: "less_dummy and greater_dummy — each is a sentinel for one chain. I'll keep tail pointers less and greater to append efficiently."

2. Emphasize greater.next = None: Walk through a case where the last greater node's original .next would cause a cycle. This shows you know the bug and why you're preventing it.

3. Test the partition boundary: Use x=3 with values [3, 1, 4]. Node 3 should go to the greater chain (>= x). Node 1 to less, node 4 to greater. Output: [1, 3, 4].

4. Connect to Quicksort: "This is the partition step of Quicksort adapted for linked lists. If you wanted to sort by value, you'd recursively partition each half."

5. State the stability: "The two-chain approach is inherently stable — nodes are added to each chain in their original traversal order, preserving relative order."

Follow-up Questions#

Q: How does this differ from Odd Even Linked List? Odd Even groups by index parity (1st, 3rd, 5th... vs 2nd, 4th, 6th...). Partition List groups by value comparison against a pivot. The two-chain technique is identical, but the condition for which chain a node joins differs.

Q: What if x is smaller than all values in the list? All nodes go to the greater chain. less tail stays at less_dummy. less.next = greater_dummy.next makes less_dummy.next = first greater node. Correct — the entire list, in original order.

Q: What if x is larger than all values? All nodes go to the less chain. greater.next = None (greater_dummy.next is still None). less.next = None. Return less_dummy.next = head. Entire list unchanged, correct.

Q: Can you do it without two dummy nodes? Yes, but with more branching. You'd initialize less_head and greater_head lazily (on first assignment), requiring if-else logic. The two dummy nodes eliminate this. Code with dummies is cleaner.

Q: What if you need to partition by multiple criteria? Use multiple chains — one per partition bucket. The same pattern extends: k dummies, k tail pointers, route each node to the correct chain, then concatenate.

Key Takeaways#

• Use two dummy head sentinels: less_dummy and greater_dummy, each starting an independent chain.
• Traverse once, appending each node to the appropriate chain — val < x goes to less, val >= x goes to greater.
• Always terminate the greater chain: greater.next = None — prevents cycles from stale .next pointers.
• Connect chains: less.next = greater_dummy.next (use the head of greater, not the tail).
• The technique is stable: relative order within each partition is preserved.
• Return less_dummy.next — the head of the combined result.