Common Linked List Patterns - Learning Module

Loading content...

0/279

Partitioning Around a Value

The Foundation of Quicksort

Partitioning is the act of rearranging elements so that all elements satisfying some condition come before all elements that don't. In the classic form: given a value x, reorganize a list so all nodes with values less than x come before nodes with values greater than or equal to x.

This operation is the heart of quicksort—the famous O(n log n) average-case sorting algorithm. Every recursive step of quicksort partitions around a pivot, then recursively sorts the two halves. Understanding partitioning deeply means understanding one of the most important algorithms in computer science.

But partitioning on linked lists is different from arrays. We can't swap elements by index. Instead, we must think about building two separate chains and joining them. This approach leads to elegant, stable solutions that preserve relative ordering—something array-based in-place partitioning often sacrifices.

What You Will Learn

By the end of this page, you will: (1) Understand partitioning as a fundamental operation, (2) Implement stable partition on linked lists, (3) Connect partitioning to quicksort and the Dutch National Flag problem, (4) Handle edge cases when all elements are less than or greater than x, (5) Recognize partitioning as a building block for sorting and selection.

The Problem Statement

Problem:

Given the head of a linked list and a value x, partition it such that all nodes with values less than x come before nodes with values greater than or equal to x.

Stability Requirement:

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

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

Explanation:
- Nodes < 3: [1, 2, 2] (relative order preserved)
- Nodes >= 3: [4, 3, 5] (relative order preserved)
- Concatenation: 1 → 2 → 2 → 4 → 3 → 5

Partition Requirements Summary
Aspect	Requirement
Input	Head of linked list, pivot value x
Output	Head of partitioned list
Partition	All nodes < x before all nodes >= x
Stability	Relative order within partitions preserved
Time Complexity	O(n) — single pass through the list
Space Complexity	O(1) — only use pointer variables

Why Stability Matters:

Stability means equal elements maintain their original relative order. In this problem, nodes equal to x should appear in their original order within the 'greater-or-equal' partition.

Stable sorting algorithms like merge sort rely on stable partitioning. Additionally, stability makes the output deterministic—the same input always produces the same output, which simplifies testing and debugging.

The Two-List Strategy

The elegant solution for linked list partitioning is to build two separate lists as we traverse:

"Less" list: All nodes with value < x
"Greater-or-equal" list: All nodes with value >= x

After traversal, concatenate the two lists: less_list → greater_list.

Why This Works:

We traverse the original list once, O(n)
Each node is appended to exactly one of the two lists
Appending preserves original order (stability)
Final concatenation is O(1)

The Dummy Node Technique:

Both lists use dummy heads to simplify the logic. Instead of checking if a list is empty before appending, we always have a valid tail to attach to.

Mental Model

Picture sorting cards into two piles: one for cards less than a target, one for cards greater or equal. You go through your hand once, placing each card on the appropriate pile. At the end, you stack the piles. That's exactly what we're doing with pointers.

Step-by-Step Visualization:

Partitioning 1 → 4 → 3 → 2 → 5 → 2 with x = 3:

Step	Node	Comparison	Less List	Greater List
1	1	1 < 3 ✓	1	(empty)
2	4	4 >= 3	1	4
3	3	3 >= 3	1	4 → 3
4	2	2 < 3 ✓	1 → 2	4 → 3
5	5	5 >= 3	1 → 2	4 → 3 → 5
6	2	2 < 3 ✓	1 → 2 → 2	4 → 3 → 5

Concatenate: 1 → 2 → 2 → 4 → 3 → 5

Implementation

partition_list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
def partition(head: ListNode, x: int) -> ListNode:
    """
    Partition linked list around value x.
    
    All nodes < x come before all nodes >= x.
    Preserves relative order within each partition (stable).
    
    Time Complexity: O(n) - single pass
    Space Complexity: O(1) - only pointer variables
    """
    # Create dummy heads for both partitions
    less_dummy = ListNode(0)      # Head for nodes < x
    greater_dummy = ListNode(0)   # Head for nodes >= x
    
    # Tails for appending
    less_tail = less_dummy
    greater_tail = greater_dummy
    
    # Traverse the original list
    current = head
    while current is not None:
        if current.val < x:
            # Append to "less" list
            less_tail.next = current
            less_tail = less_tail.next
        else:
            # Append to "greater-or-equal" list
            greater_tail.next = current
            greater_tail = greater_tail.next
        
        # Move to next node
        current = current.next
    
    # CRITICAL: Terminate the greater list
    # Without this, we might have a cycle or extra nodes
    greater_tail.next = None
    
    # Concatenate: less list → greater list
    less_tail.next = greater_dummy.next
    
    # Return head of the merged list (skip dummy)
    return less_dummy.next
 
 
def partition_verbose(head: ListNode, x: int) -> ListNode:
    """
    Same algorithm with detailed comments for learning.
    """
    # Dummy nodes eliminate edge cases for empty partitions
    # If all nodes are >= x, less_dummy.next will be None
    # If all nodes are < x, greater_dummy.next will be None
    less_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    
    # Tail pointers: always point to the last node of each list
    less_tail = less_dummy
    greater_tail = greater_dummy
    
    # Traverse and distribute nodes
    while head:
        # Save next before we potentially modify head.next
        next_node = head.next
        
        if head.val < x:
            less_tail.next = head
            less_tail = head
        else:
            greater_tail.next = head
            greater_tail = head
        
        head = next_node
    
    # Essential: cut off the greater list from any hanging references
    greater_tail.next = None
    
    # Connect less list to greater list
    less_tail.next = greater_dummy.next
    
    return less_dummy.next

Critical: Terminate the Greater List

The line greater_tail.next = None is essential. Without it, the last node of the greater list might still point to some node in the less list (from the original structure), creating a cycle. Always explicitly terminate lists you build.

Edge Cases

Let's explore the edge cases and verify our solution handles them:

Edge Case 1: Empty List

Input: None, x = 5
Output: None

With dummy nodes, this works naturally—both lists remain as just their dummies.

Edge Case 2: All Nodes Less Than x

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

The greater list is empty. less_tail.next = greater_dummy.next sets less_tail.next = None.

Edge Case 3: All Nodes Greater Than or Equal to x

Input: 5 → 6 → 7, x = 3
Output: 5 → 6 → 7

The less list is empty. less_dummy.next = greater_dummy.next correctly returns the greater list.

Edge Case 4: Single Node

Input: 5, x = 5
Output: 5 (in greater-or-equal partition)

Input: 5, x = 10
Output: 5 (in less partition)

Edge Case 5: All Nodes Equal to x

Input: 3 → 3 → 3, x = 3
Output: 3 → 3 → 3 (all in greater-or-equal)

partition_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def test_partition_edge_cases():
    """Comprehensive edge case testing."""
    
    def create_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        curr = head
        for val in values[1:]:
            curr.next = ListNode(val)
            curr = curr.next
        return head
    
    def to_array(head):
        result = []
        while head:
            result.append(head.val)
            head = head.next
        return result
    
    # Test 1: Standard case from problem
    result = partition(create_list([1,4,3,2,5,2]), 3)
    assert to_array(result) == [1,2,2,4,3,5], "Standard case failed"
    
    # Test 2: Empty list
    result = partition(None, 5)
    assert result is None, "Empty list failed"
    
    # Test 3: All less than x
    result = partition(create_list([1,2,3]), 5)
    assert to_array(result) == [1,2,3], "All less than x failed"
    
    # Test 4: All greater than or equal to x
    result = partition(create_list([5,6,7]), 3)
    assert to_array(result) == [5,6,7], "All >= x failed"
    
    # Test 5: Single node (less)
    result = partition(create_list([1]), 5)
    assert to_array(result) == [1], "Single node < x failed"
    
    # Test 6: Single node (greater-equal)
    result = partition(create_list([5]), 5)
    assert to_array(result) == [5], "Single node >= x failed"
    
    # Test 7: All equal to x
    result = partition(create_list([3,3,3]), 3)
    assert to_array(result) == [3,3,3], "All equal to x failed"
    
    # Test 8: Already partitioned
    result = partition(create_list([1,2,4,5]), 3)
    assert to_array(result) == [1,2,4,5], "Already partitioned failed"
    
    # Test 9: Reverse order
    result = partition(create_list([5,4,3,2,1]), 3)
    assert to_array(result) == [2,1,5,4,3], "Reverse order failed"
    
    print("All partition tests passed! ✓")

The Beauty of Dummy Nodes

Notice how dummy nodes eliminate special-case code. Whether a partition is empty, has one node, or has many—the code is identical. This uniformity makes the algorithm easier to write, understand, and debug.

Connection to Quicksort

Partitioning is the central operation in quicksort. Understanding this connection illuminates both algorithms:

Quicksort's Structure:

Choose a pivot from the array/list
Partition elements: < pivot | pivot | > pivot
Recursively sort the left and right partitions
Concatenate (implicitly, since we're in-place)

Linked List Quicksort:

Unlike array quicksort which partitions in-place using swaps, linked list quicksort naturally uses the two-list approach we just learned.

quicksort_linkedlist.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def quicksort_list(head: ListNode) -> ListNode:
    """
    Sort a linked list using quicksort.
    
    Time Complexity: O(n log n) average, O(n²) worst case
    Space Complexity: O(log n) for recursion stack (average)
    
    Note: Merge sort is generally preferred for linked lists
    due to guaranteed O(n log n) and better cache behavior.
    """
    # Base case: empty or single node
    if not head or not head.next:
        return head
    
    # Choose pivot (use first node for simplicity)
    pivot = head
    head = head.next  # Remove pivot from list
    pivot.next = None
    
    # Partition into three lists: less, equal, greater
    less_dummy = ListNode(0)
    equal_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    
    less_tail = less_dummy
    equal_tail = equal_dummy
    greater_tail = greater_dummy
    
    # Add pivot to equal list
    equal_tail.next = pivot
    equal_tail = pivot
    
    # Distribute nodes
    while head:
        next_node = head.next
        head.next = None
        
        if head.val < pivot.val:
            less_tail.next = head
            less_tail = head
        elif head.val > pivot.val:
            greater_tail.next = head
            greater_tail = head
        else:
            equal_tail.next = head
            equal_tail = head
        
        head = next_node
    
    # Recursively sort less and greater partitions
    less_sorted = quicksort_list(less_dummy.next)
    greater_sorted = quicksort_list(greater_dummy.next)
    
    # Find tail of less_sorted for concatenation
    if less_sorted:
        tail = less_sorted
        while tail.next:
            tail = tail.next
        tail.next = equal_dummy.next
    else:
        less_sorted = equal_dummy.next
    
    # Find tail of equal for concatenation
    equal_tail.next = greater_sorted
    
    return less_sorted or equal_dummy.next

Quicksort vs Merge Sort for Linked Lists
Aspect	Quicksort	Merge Sort
Time (average)	O(n log n)	O(n log n)
Time (worst)	O(n²)	O(n log n)
Stability	Stable with care	Naturally stable
Pivot selection	Critical for performance	Not applicable
Practical use	Rare for linked lists	Preferred choice

Why Merge Sort is Preferred

For linked lists, merge sort is typically preferred over quicksort because: (1) Finding the middle for merge sort is O(n) and splits evenly, while choosing a good pivot for quicksort is harder. (2) Merge sort guarantees O(n log n) worst case. (3) Merge itself is O(1) space for linked lists, leveraging the natural flexibility of pointer manipulation.

Three-Way Partition — Dutch National Flag

A powerful extension of two-way partitioning is three-way partitioning, famously known as the Dutch National Flag problem (named by Edsger Dijkstra for the three-colored flag of the Netherlands).

Problem:

Given an array/list with elements that can be classified into three categories (say: less than, equal to, and greater than a pivot), rearrange so all elements of each category are grouped together.

For Linked Lists:

We simply extend our two-list approach to three lists: less, equal, and greater. The stability requirement makes linked lists ideal for this problem.

three_way_partition.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
def three_way_partition(head: ListNode, x: int) -> ListNode:
    """
    Partition linked list into three sections:
    [less than x] → [equal to x] → [greater than x]
    
    This is stable: relative order within each section is preserved.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Three lists with dummy heads
    less_dummy = ListNode(0)
    equal_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    
    # Tail pointers
    less_tail = less_dummy
    equal_tail = equal_dummy
    greater_tail = greater_dummy
    
    # Distribute nodes
    while head:
        next_node = head.next
        
        if head.val < x:
            less_tail.next = head
            less_tail = head
        elif head.val == x:
            equal_tail.next = head
            equal_tail = head
        else:
            greater_tail.next = head
            greater_tail = head
        
        head = next_node
    
    # Terminate all lists
    greater_tail.next = None
    
    # Concatenate: less → equal → greater
    # Handle cases where some lists might be empty
    equal_tail.next = greater_dummy.next
    less_tail.next = equal_dummy.next
    
    return less_dummy.next or equal_dummy.next or greater_dummy.next
 
 
def dutch_national_flag(head: ListNode) -> ListNode:
    """
    Classic Dutch National Flag: partition 0s, 1s, and 2s.
    
    Example: 2 → 0 → 1 → 2 → 0 → 1 → 0
    Result:  0 → 0 → 0 → 1 → 1 → 2 → 2
    """
    zeros = ListNode(0)
    ones = ListNode(0)
    twos = ListNode(0)
    
    zeros_tail = zeros
    ones_tail = ones
    twos_tail = twos
    
    while head:
        next_node = head.next
        
        if head.val == 0:
            zeros_tail.next = head
            zeros_tail = head
        elif head.val == 1:
            ones_tail.next = head
            ones_tail = head
        else:
            twos_tail.next = head
            twos_tail = head
        
        head = next_node
    
    # Concatenate
    twos_tail.next = None
    ones_tail.next = twos.next
    zeros_tail.next = ones.next
    
    return zeros.next or ones.next or twos.next

Extension to K Categories

The pattern extends naturally to k categories: create k lists, distribute nodes, concatenate. This is useful for problems like sorting by specific keys, grouping by attribute, or bucket sort variants. The time complexity remains O(n), and space is O(1) since we're just using a fixed number of pointer variables.

Common Mistakes and How to Avoid Them

Classic Mistakes in Partitioning

•Forgetting to terminate the last list — The last node in the 'greater' list might still point to a node in the 'less' list (from the original structure). Always set greater_tail.next = None.
•Wrong comparison operator — Using <= instead of < changes which partition nodes go to. Read the problem carefully: is it '<' or '<='?
•Not handling empty partitions — If all nodes are >= x, the less list is empty. Returning less_dummy.next (which is None) would be wrong—but our concatenation handles this correctly.
•Modifying next pointer before saving — Always save current.next before reassigning current.next. Otherwise you lose the reference to the rest of the list.
•Creating nodes instead of rewiring — This is a rewiring problem, not a copying problem. Don't create new ListNode objects—reuse the existing ones.
•Forgetting stability — In-place array partitioning often loses stability. Linked list partitioning via two-list approach is naturally stable—preserve this property.

The Cycle Bug

The most insidious bug is forgetting to terminate the last list. Your function might return a 'correct' list that secretly has a cycle. Tests might pass superficially but infinite loops lurk. Always explicitly set the tail's next to None.

Complexity Analysis

Time Complexity: O(n)

We traverse the list exactly once: O(n)
Each node is processed in O(1): one comparison, two pointer assignments
No nested loops, no multiple traversals
Concatenation is O(1): just pointer assignments

Space Complexity: O(1)

We use a fixed number of pointer variables (4 dummy + 4 tail = 8)
No additional data structures that grow with input size
No recursion (and thus no call stack usage)

Why This is Optimal:

We must examine every node to make the partition decision: Ω(n) lower bound
We achieve this with a single pass: O(n) upper bound
Thus: Θ(n) is optimal

Comparison with Array-Based Partitioning
Aspect	Linked List	Array (In-Place)
Time	O(n)	O(n)
Space	O(1)	O(1)
Stability	Naturally stable	Not stable (Lomuto/Hoare)
Technique	Two-list collection	Swap-based
Cache behavior	Poor (pointer chasing)	Good (contiguous)

The Stability Trade-off

Array-based in-place partitioning (Lomuto or Hoare schemes) sacrifices stability for minimal space usage. Linked list partitioning via two-list approach achieves stability effortlessly. This is one of the few cases where linked lists have an advantage over arrays.

Applications Beyond Sorting

Partitioning appears in many contexts beyond sorting:

Partition Applications

•Quickselect — Finding the kth smallest element in O(n) average time uses repeated partitioning to narrow down the search space.
•Separating positives and negatives — Business logic often requires grouping data: active vs inactive users, paid vs free accounts.
•Move zeros to end — A common interview problem: partition around 0 with slight modification.
•Odd-even separation — Partition by parity: all odd numbers before all even numbers.
•Grouping by attribute — Any categorical grouping can be viewed as partitioning: by status, priority, type.
•Priority segregation — In task systems, high-priority items before low-priority items.

partition_variations.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def partition_odd_even(head: ListNode) -> ListNode:
    """Partition list into odd values followed by even values."""
    odd_dummy = ListNode(0)
    even_dummy = ListNode(0)
    odd_tail = odd_dummy
    even_tail = even_dummy
    
    while head:
        next_node = head.next
        if head.val % 2 == 1:
            odd_tail.next = head
            odd_tail = head
        else:
            even_tail.next = head
            even_tail = head
        head = next_node
    
    even_tail.next = None
    odd_tail.next = even_dummy.next
    return odd_dummy.next or even_dummy.next
 
 
def move_zeros_to_end(head: ListNode) -> ListNode:
    """Move all zero-valued nodes to the end of the list."""
    non_zero = ListNode(0)
    zero = ListNode(0)
    nz_tail = non_zero
    z_tail = zero
    
    while head:
        next_node = head.next
        if head.val != 0:
            nz_tail.next = head
            nz_tail = head
        else:
            z_tail.next = head
            z_tail = head
        head = next_node
    
    z_tail.next = None
    nz_tail.next = zero.next
    return non_zero.next or zero.next

Summary: Mastering List Partitioning

Partitioning is a fundamental operation that connects linked list manipulation to some of the most important algorithms in computer science. Let's consolidate the key insights:

Key Takeaways

•Build two (or more) lists and concatenate — This is the natural approach for linked list partitioning, achieving O(n) time and O(1) space.
•Dummy nodes eliminate edge cases — Whether a partition is empty or full, the code remains uniform.
•Always terminate the last list — Set greater_tail.next = None to prevent cycles from the original structure.
•Linked list partitioning is naturally stable — Appending nodes preserves their original relative order.
•Partitioning is the heart of quicksort — Understanding partitioning illuminates this fundamental sorting algorithm.
•The pattern extends to k-way partitioning — Dutch National Flag, categorical grouping, priority segregation all use the same approach.

What's Next:

In the final page of this module, we'll explore Palindrome Detection—determining whether a linked list reads the same forwards and backwards. This problem synthesizes reversal, two-pointer techniques, and careful middle-finding into an elegant solution.

Page Complete

You've mastered linked list partitioning—the heart of quicksort and a versatile pattern for any categorical grouping. You understand the two-list approach, stability guarantees, and extensions to three-way and k-way partitioning. This pattern is now part of your algorithmic toolkit.

Partitioning Around a Value

The Foundation of Quicksort

What You Will Learn

The Problem Statement

Problem:

Given the head of a linked list and a value x, partition it such that all nodes with values less than x come before nodes with values greater than or equal to x.

Stability Requirement:

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

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

Explanation:
- Nodes < 3: [1, 2, 2] (relative order preserved)
- Nodes >= 3: [4, 3, 5] (relative order preserved)
- Concatenation: 1 → 2 → 2 → 4 → 3 → 5

Partition Requirements Summary
Aspect	Requirement
Input	Head of linked list, pivot value x
Output	Head of partitioned list
Partition	All nodes < x before all nodes >= x
Stability	Relative order within partitions preserved
Time Complexity	O(n) — single pass through the list
Space Complexity	O(1) — only use pointer variables

Why Stability Matters:

Stability means equal elements maintain their original relative order. In this problem, nodes equal to x should appear in their original order within the 'greater-or-equal' partition.

The Two-List Strategy

The elegant solution for linked list partitioning is to build two separate lists as we traverse:

"Less" list: All nodes with value < x
"Greater-or-equal" list: All nodes with value >= x

After traversal, concatenate the two lists: less_list → greater_list.

Why This Works:

We traverse the original list once, O(n)
Each node is appended to exactly one of the two lists
Appending preserves original order (stability)
Final concatenation is O(1)

The Dummy Node Technique:

Both lists use dummy heads to simplify the logic. Instead of checking if a list is empty before appending, we always have a valid tail to attach to.

Mental Model

Step-by-Step Visualization:

Partitioning 1 → 4 → 3 → 2 → 5 → 2 with x = 3:

Step	Node	Comparison	Less List	Greater List
1	1	1 < 3 ✓	1	(empty)
2	4	4 >= 3	1	4
3	3	3 >= 3	1	4 → 3
4	2	2 < 3 ✓	1 → 2	4 → 3
5	5	5 >= 3	1 → 2	4 → 3 → 5
6	2	2 < 3 ✓	1 → 2 → 2	4 → 3 → 5

Concatenate: 1 → 2 → 2 → 4 → 3 → 5

Implementation

partition_list.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
def partition(head: ListNode, x: int) -> ListNode:
    """
    Partition linked list around value x.
    
    All nodes < x come before all nodes >= x.
    Preserves relative order within each partition (stable).
    
    Time Complexity: O(n) - single pass
    Space Complexity: O(1) - only pointer variables
    """
    # Create dummy heads for both partitions
    less_dummy = ListNode(0)      # Head for nodes < x
    greater_dummy = ListNode(0)   # Head for nodes >= x
    
    # Tails for appending
    less_tail = less_dummy
    greater_tail = greater_dummy
    
    # Traverse the original list
    current = head
    while current is not None:
        if current.val < x:
            # Append to "less" list
            less_tail.next = current
            less_tail = less_tail.next
        else:
            # Append to "greater-or-equal" list
            greater_tail.next = current
            greater_tail = greater_tail.next
        
        # Move to next node
        current = current.next
    
    # CRITICAL: Terminate the greater list
    # Without this, we might have a cycle or extra nodes
    greater_tail.next = None
    
    # Concatenate: less list → greater list
    less_tail.next = greater_dummy.next
    
    # Return head of the merged list (skip dummy)
    return less_dummy.next
 
 
def partition_verbose(head: ListNode, x: int) -> ListNode:
    """
    Same algorithm with detailed comments for learning.
    """
    # Dummy nodes eliminate edge cases for empty partitions
    # If all nodes are >= x, less_dummy.next will be None
    # If all nodes are < x, greater_dummy.next will be None
    less_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    
    # Tail pointers: always point to the last node of each list
    less_tail = less_dummy
    greater_tail = greater_dummy
    
    # Traverse and distribute nodes
    while head:
        # Save next before we potentially modify head.next
        next_node = head.next
        
        if head.val < x:
            less_tail.next = head
            less_tail = head
        else:
            greater_tail.next = head
            greater_tail = head
        
        head = next_node
    
    # Essential: cut off the greater list from any hanging references
    greater_tail.next = None
    
    # Connect less list to greater list
    less_tail.next = greater_dummy.next
    
    return less_dummy.next

Critical: Terminate the Greater List

Edge Cases

Let's explore the edge cases and verify our solution handles them:

Edge Case 1: Empty List

Input: None, x = 5
Output: None

With dummy nodes, this works naturally—both lists remain as just their dummies.

Edge Case 2: All Nodes Less Than x

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

The greater list is empty. less_tail.next = greater_dummy.next sets less_tail.next = None.

Edge Case 3: All Nodes Greater Than or Equal to x

Input: 5 → 6 → 7, x = 3
Output: 5 → 6 → 7

The less list is empty. less_dummy.next = greater_dummy.next correctly returns the greater list.

Edge Case 4: Single Node

Input: 5, x = 5
Output: 5 (in greater-or-equal partition)

Input: 5, x = 10
Output: 5 (in less partition)

Edge Case 5: All Nodes Equal to x

Input: 3 → 3 → 3, x = 3
Output: 3 → 3 → 3 (all in greater-or-equal)

partition_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def test_partition_edge_cases():
    """Comprehensive edge case testing."""
    
    def create_list(values):
        if not values:
            return None
        head = ListNode(values[0])
        curr = head
        for val in values[1:]:
            curr.next = ListNode(val)
            curr = curr.next
        return head
    
    def to_array(head):
        result = []
        while head:
            result.append(head.val)
            head = head.next
        return result
    
    # Test 1: Standard case from problem
    result = partition(create_list([1,4,3,2,5,2]), 3)
    assert to_array(result) == [1,2,2,4,3,5], "Standard case failed"
    
    # Test 2: Empty list
    result = partition(None, 5)
    assert result is None, "Empty list failed"
    
    # Test 3: All less than x
    result = partition(create_list([1,2,3]), 5)
    assert to_array(result) == [1,2,3], "All less than x failed"
    
    # Test 4: All greater than or equal to x
    result = partition(create_list([5,6,7]), 3)
    assert to_array(result) == [5,6,7], "All >= x failed"
    
    # Test 5: Single node (less)
    result = partition(create_list([1]), 5)
    assert to_array(result) == [1], "Single node < x failed"
    
    # Test 6: Single node (greater-equal)
    result = partition(create_list([5]), 5)
    assert to_array(result) == [5], "Single node >= x failed"
    
    # Test 7: All equal to x
    result = partition(create_list([3,3,3]), 3)
    assert to_array(result) == [3,3,3], "All equal to x failed"
    
    # Test 8: Already partitioned
    result = partition(create_list([1,2,4,5]), 3)
    assert to_array(result) == [1,2,4,5], "Already partitioned failed"
    
    # Test 9: Reverse order
    result = partition(create_list([5,4,3,2,1]), 3)
    assert to_array(result) == [2,1,5,4,3], "Reverse order failed"
    
    print("All partition tests passed! ✓")

The Beauty of Dummy Nodes

Connection to Quicksort

Partitioning is the central operation in quicksort. Understanding this connection illuminates both algorithms:

Quicksort's Structure:

Choose a pivot from the array/list
Partition elements: < pivot | pivot | > pivot
Recursively sort the left and right partitions
Concatenate (implicitly, since we're in-place)

Linked List Quicksort:

Unlike array quicksort which partitions in-place using swaps, linked list quicksort naturally uses the two-list approach we just learned.

quicksort_linkedlist.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def quicksort_list(head: ListNode) -> ListNode:
    """
    Sort a linked list using quicksort.
    
    Time Complexity: O(n log n) average, O(n²) worst case
    Space Complexity: O(log n) for recursion stack (average)
    
    Note: Merge sort is generally preferred for linked lists
    due to guaranteed O(n log n) and better cache behavior.
    """
    # Base case: empty or single node
    if not head or not head.next:
        return head
    
    # Choose pivot (use first node for simplicity)
    pivot = head
    head = head.next  # Remove pivot from list
    pivot.next = None
    
    # Partition into three lists: less, equal, greater
    less_dummy = ListNode(0)
    equal_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    
    less_tail = less_dummy
    equal_tail = equal_dummy
    greater_tail = greater_dummy
    
    # Add pivot to equal list
    equal_tail.next = pivot
    equal_tail = pivot
    
    # Distribute nodes
    while head:
        next_node = head.next
        head.next = None
        
        if head.val < pivot.val:
            less_tail.next = head
            less_tail = head
        elif head.val > pivot.val:
            greater_tail.next = head
            greater_tail = head
        else:
            equal_tail.next = head
            equal_tail = head
        
        head = next_node
    
    # Recursively sort less and greater partitions
    less_sorted = quicksort_list(less_dummy.next)
    greater_sorted = quicksort_list(greater_dummy.next)
    
    # Find tail of less_sorted for concatenation
    if less_sorted:
        tail = less_sorted
        while tail.next:
            tail = tail.next
        tail.next = equal_dummy.next
    else:
        less_sorted = equal_dummy.next
    
    # Find tail of equal for concatenation
    equal_tail.next = greater_sorted
    
    return less_sorted or equal_dummy.next

Quicksort vs Merge Sort for Linked Lists
Aspect	Quicksort	Merge Sort
Time (average)	O(n log n)	O(n log n)
Time (worst)	O(n²)	O(n log n)
Stability	Stable with care	Naturally stable
Pivot selection	Critical for performance	Not applicable
Practical use	Rare for linked lists	Preferred choice

Why Merge Sort is Preferred

Three-Way Partition — Dutch National Flag

Problem:

Given an array/list with elements that can be classified into three categories (say: less than, equal to, and greater than a pivot), rearrange so all elements of each category are grouped together.

For Linked Lists:

We simply extend our two-list approach to three lists: less, equal, and greater. The stability requirement makes linked lists ideal for this problem.

three_way_partition.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
def three_way_partition(head: ListNode, x: int) -> ListNode:
    """
    Partition linked list into three sections:
    [less than x] → [equal to x] → [greater than x]
    
    This is stable: relative order within each section is preserved.
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Three lists with dummy heads
    less_dummy = ListNode(0)
    equal_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    
    # Tail pointers
    less_tail = less_dummy
    equal_tail = equal_dummy
    greater_tail = greater_dummy
    
    # Distribute nodes
    while head:
        next_node = head.next
        
        if head.val < x:
            less_tail.next = head
            less_tail = head
        elif head.val == x:
            equal_tail.next = head
            equal_tail = head
        else:
            greater_tail.next = head
            greater_tail = head
        
        head = next_node
    
    # Terminate all lists
    greater_tail.next = None
    
    # Concatenate: less → equal → greater
    # Handle cases where some lists might be empty
    equal_tail.next = greater_dummy.next
    less_tail.next = equal_dummy.next
    
    return less_dummy.next or equal_dummy.next or greater_dummy.next
 
 
def dutch_national_flag(head: ListNode) -> ListNode:
    """
    Classic Dutch National Flag: partition 0s, 1s, and 2s.
    
    Example: 2 → 0 → 1 → 2 → 0 → 1 → 0
    Result:  0 → 0 → 0 → 1 → 1 → 2 → 2
    """
    zeros = ListNode(0)
    ones = ListNode(0)
    twos = ListNode(0)
    
    zeros_tail = zeros
    ones_tail = ones
    twos_tail = twos
    
    while head:
        next_node = head.next
        
        if head.val == 0:
            zeros_tail.next = head
            zeros_tail = head
        elif head.val == 1:
            ones_tail.next = head
            ones_tail = head
        else:
            twos_tail.next = head
            twos_tail = head
        
        head = next_node
    
    # Concatenate
    twos_tail.next = None
    ones_tail.next = twos.next
    zeros_tail.next = ones.next
    
    return zeros.next or ones.next or twos.next

Extension to K Categories

Common Mistakes and How to Avoid Them

Classic Mistakes in Partitioning

•Forgetting to terminate the last list — The last node in the 'greater' list might still point to a node in the 'less' list (from the original structure). Always set greater_tail.next = None.
•Wrong comparison operator — Using <= instead of < changes which partition nodes go to. Read the problem carefully: is it '<' or '<='?
•Not handling empty partitions — If all nodes are >= x, the less list is empty. Returning less_dummy.next (which is None) would be wrong—but our concatenation handles this correctly.
•Modifying next pointer before saving — Always save current.next before reassigning current.next. Otherwise you lose the reference to the rest of the list.
•Creating nodes instead of rewiring — This is a rewiring problem, not a copying problem. Don't create new ListNode objects—reuse the existing ones.
•Forgetting stability — In-place array partitioning often loses stability. Linked list partitioning via two-list approach is naturally stable—preserve this property.

The Cycle Bug

Complexity Analysis

Time Complexity: O(n)

We traverse the list exactly once: O(n)
Each node is processed in O(1): one comparison, two pointer assignments
No nested loops, no multiple traversals
Concatenation is O(1): just pointer assignments

Space Complexity: O(1)

We use a fixed number of pointer variables (4 dummy + 4 tail = 8)
No additional data structures that grow with input size
No recursion (and thus no call stack usage)

Why This is Optimal:

We must examine every node to make the partition decision: Ω(n) lower bound
We achieve this with a single pass: O(n) upper bound
Thus: Θ(n) is optimal

Comparison with Array-Based Partitioning
Aspect	Linked List	Array (In-Place)
Time	O(n)	O(n)
Space	O(1)	O(1)
Stability	Naturally stable	Not stable (Lomuto/Hoare)
Technique	Two-list collection	Swap-based
Cache behavior	Poor (pointer chasing)	Good (contiguous)

The Stability Trade-off

Applications Beyond Sorting

Partitioning appears in many contexts beyond sorting:

Partition Applications

•Quickselect — Finding the kth smallest element in O(n) average time uses repeated partitioning to narrow down the search space.
•Separating positives and negatives — Business logic often requires grouping data: active vs inactive users, paid vs free accounts.
•Move zeros to end — A common interview problem: partition around 0 with slight modification.
•Odd-even separation — Partition by parity: all odd numbers before all even numbers.
•Grouping by attribute — Any categorical grouping can be viewed as partitioning: by status, priority, type.
•Priority segregation — In task systems, high-priority items before low-priority items.

partition_variations.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def partition_odd_even(head: ListNode) -> ListNode:
    """Partition list into odd values followed by even values."""
    odd_dummy = ListNode(0)
    even_dummy = ListNode(0)
    odd_tail = odd_dummy
    even_tail = even_dummy
    
    while head:
        next_node = head.next
        if head.val % 2 == 1:
            odd_tail.next = head
            odd_tail = head
        else:
            even_tail.next = head
            even_tail = head
        head = next_node
    
    even_tail.next = None
    odd_tail.next = even_dummy.next
    return odd_dummy.next or even_dummy.next
 
 
def move_zeros_to_end(head: ListNode) -> ListNode:
    """Move all zero-valued nodes to the end of the list."""
    non_zero = ListNode(0)
    zero = ListNode(0)
    nz_tail = non_zero
    z_tail = zero
    
    while head:
        next_node = head.next
        if head.val != 0:
            nz_tail.next = head
            nz_tail = head
        else:
            z_tail.next = head
            z_tail = head
        head = next_node
    
    z_tail.next = None
    nz_tail.next = zero.next
    return non_zero.next or zero.next

Summary: Mastering List Partitioning

Partitioning is a fundamental operation that connects linked list manipulation to some of the most important algorithms in computer science. Let's consolidate the key insights:

Key Takeaways

•Build two (or more) lists and concatenate — This is the natural approach for linked list partitioning, achieving O(n) time and O(1) space.
•Dummy nodes eliminate edge cases — Whether a partition is empty or full, the code remains uniform.
•Always terminate the last list — Set greater_tail.next = None to prevent cycles from the original structure.
•Linked list partitioning is naturally stable — Appending nodes preserves their original relative order.
•Partitioning is the heart of quicksort — Understanding partitioning illuminates this fundamental sorting algorithm.
•The pattern extends to k-way partitioning — Dutch National Flag, categorical grouping, priority segregation all use the same approach.

What's Next:

Page Complete