Partition List

Difficulty: Medium
Topics: Linked List, Two Pointers
Link: https://leetcode.com/problems/partition-list/

Problem Description

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.

Example 1:


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

Example 2:


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

Constraints:

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

Solution

1. Problem Deconstruction

Technical Restatement: Given a singly-linked list data structure where each node contains an integer value and a reference to the next node, reorganize the list such that all nodes with values strictly less than a given threshold x appear before all nodes with values greater than or equal to x, while maintaining the original relative ordering of nodes within each partition group. The algorithm must operate in-place with constant auxiliary space complexity.

Beginner-Friendly Explanation: Imagine you have a chain of numbered boxes where each box points to the next one. You’re given a special number x. Your task is to rearrange the chain so that all boxes with numbers smaller than x come first, followed by boxes with numbers equal to or larger than x. Crucially, within each group, the boxes must keep their original sequence. For example, if box #4 originally came before box #2 in the “small numbers” group, they should maintain that order after rearrangement.

Mathematical Formulation: Let L = {v₁ → v₂ → ... → vₙ} be a linked list of length n, and let x ∈ ℤ be the partition threshold. We seek a permutation L' such that:

∀ vᵢ, vⱼ ∈ L' where vᵢ < x ∧ vⱼ ≥ x, index i < j
For any vₐ, v_b where (vₐ < x ∧ v_b < x) ∨ (vₐ ≥ x ∧ v_b ≥ x), their relative positions satisfy: pos(vₐ) < pos(v_b) ⇔ original_pos(vₐ) < original_pos(v_b)

Constraint Analysis:

Number of nodes [0, 200]: Permits O(n²) solutions but expects O(n) optimal. Empty list (n=0) is valid edge case.
Node values [-100, 100]: No overflow concerns. Negative values possible.
x ∈ [-200, 200]: Threshold can be outside node value range (e.g., all nodes < x or all ≥ x).
Hidden edge cases:
- All nodes less than x (output = input)
- All nodes greater/equal to x (output = input)
- Single-node lists (trivial partition)
- x smaller/larger than all node values
- Multiple nodes with value exactly x

2. Intuition Scaffolding

Real-World Metaphor: Imagine organizing a school photo where students shorter than 5 feet must stand in front, with taller students behind. Within each height group, students maintain their original classroom line order. The photographer (algorithm) must efficiently rearrange the single line into two ordered segments.

Gaming Analogy: In a RPG inventory system, items below a certain value threshold (common items) should appear before premium items, while keeping each category’s discovery order intact. The player needs to scan their inventory once to separate items without losing track of either group.

Math Analogy: This is equivalent to applying a stable partition operation from sorting theory to a linked list - all elements satisfying predicate P(v) = (v < x) come before those satisfying ¬P(v), with stability preserving relative order within partitions.

Common Pitfalls:

Swapping values: Violates “preserve original nodes” requirement if interpreted strictly
Reverse ordering: Failing to maintain relative order within partitions
Single-pass confusion: Attempting to rearrange in one pass without temporary markers
Edge case oversight: Not handling empty lists or single-partition lists
Memory leaks: Losing node references during rearrangement

3. Approach Encyclopedia

Brute Force Approach:

# Collect values, partition array, rebuild list
def partition_brute(head, x):
    if not head: return None
    
    # O(n) space collection
    values = []
    curr = head
    while curr:
        values.append(curr.val)
        curr = curr.next
    
    # O(n) partitioning
    less = [v for v in values if v < x]
    geq = [v for v in values if v >= x]
    
    # O(n) reconstruction
    dummy = ListNode(0)
    curr = dummy
    for v in less + geq:
        curr.next = ListNode(v)
        curr = curr.next
    
    return dummy.next

Complexity: Time O(n), Space O(n) - violates in-place requirement

Optimal Two-Pointer Approach:

Input: 1→4→3→2→5→2, x=3

Step 1: Initialize dummy nodes
less_dummy → ... 
geq_dummy → ...

Step 2: Traverse original list
Node 1: <3 → less_dummy→1
Node 4: ≥3 → geq_dummy→4  
Node 3: ≥3 → geq_dummy→4→3
Node 2: <3 → less_dummy→1→2
Node 5: ≥3 → geq_dummy→4→3→5
Node 2: <3 → less_dummy→1→2→2

Step 3: Connect partitions
less_dummy→1→2→2→(geq_dummy→4→3→5)

Step 4: Cleanup tails
Result: 1→2→2→4→3→5

Complexity Proof:

Time: Single traversal O(n) where n = list length
Space: O(1) auxiliary space (only dummy nodes + pointers)

4. Code Deep Dive

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def partition(head, x):
    # Edge case: empty list or single node
    if not head or not head.next:
        return head
    
    # Initialize dummy heads for both partitions
    less_dummy = ListNode(0)    # Tracks nodes < x
    geq_dummy = ListNode(0)     # Tracks nodes >= x
    
    less_ptr = less_dummy       # Current end of less-than partition
    geq_ptr = geq_dummy         # Current end of geq partition
    curr = head                 # Traversal pointer
    
    while curr:
        if curr.val < x:
            less_ptr.next = curr    # Append to less-than partition
            less_ptr = less_ptr.next
        else:
            geq_ptr.next = curr     # Append to geq partition  
            geq_ptr = geq_ptr.next
        
        curr = curr.next
    
    # Connect the two partitions
    less_ptr.next = geq_dummy.next  # Less partition → geq partition
    geq_ptr.next = None             # Terminate final node
    
    return less_dummy.next

Edge Case Handling:

Example 1 [1,4,3,2,5,2], x=3:
- Line 18-20: Nodes 1,2,2 go to less partition
- Line 22-24: Nodes 4,3,5 go to geq partition
- Line 28: Connects 2→4
Example 2 [2,1], x=2:
- Node 1 (<2) → less partition
- Node 2 (≥2) → geq partition
- Result: 1→2
All nodes < x: geq_dummy.next remains None, less_ptr connects to None
All nodes ≥ x: less_dummy.next remains None, return geq_dummy.next

5. Complexity War Room

Hardware-Aware Analysis:

At maximum n=200 nodes, with typical ListNode size of 24 bytes (Python object overhead + val + next reference), total memory ≈ 4.8KB
The algorithm uses only 4 pointers (8 bytes each) + 2 dummy nodes, fitting comfortably in L1 cache (typically 32-64KB)
Single linear pass exhibits excellent cache locality

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n)	O(n)	10/10	❌ Space inefficient
Two-Pointer	O(n)	O(1)	8/10	✅ Optimal solution
In-place Swap	O(n²)	O(1)	4/10	❌ Too complex

6. Pro Mode Extras

Variants & Extensions:

Partition Around Range: a ≤ nodes ≤ b in middle, others on sides
Three-Way Partition: Dutch national flag variant for linked lists
K-Partition: Split into k ranges based on multiple thresholds
Stable Sort: Maintain relative order for equal elements

Interview Cheat Sheet:

First Mention: “This is a stable partition problem requiring O(n) time, O(1) space”
Key Insight: “We can maintain two separate chains and concatenate them”
Edge Cases: “Handle empty lists, single partitions, and tail termination”
Testing Strategy: “Verify with all-less, all-geq, and mixed cases”
Optimization Path: “Two-pointer approach avoids value swapping and maintains stability”

Common Follow-ups:

“How would you handle doubly-linked lists?” (Update prev pointers)
“What if you couldn’t use dummy nodes?” (Handle empty partition edge cases)
“How to make this generic for any data type?” (Use comparator function)

#86 - Partition List