Partition and Rearrange Linked Lists

Partitioning a linked list means rearranging nodes into groups based on some condition — all nodes less than a value come before nodes greater than or equal to it, or all odd-positioned nodes come before even-positioned ones. These problems appear frequently in interviews and teach you the powerful two-list-then-join technique.

The Core Idea: Two Dummy Lists

The cleanest way to partition a linked list is to maintain two separate lists (using dummy head nodes), distribute nodes into the appropriate list, and then join them:

# Pseudocode for any partition problem:
less_dummy = ListNode(0)    # Dummy head for "less" group
greater_dummy = ListNode(0) # Dummy head for "greater" group
less_tail = less_dummy
greater_tail = greater_dummy

for each node in original list:
    if node belongs to "less" group:
        less_tail.next = node
        less_tail = node
    else:
        greater_tail.next = node
        greater_tail = node

# Join the two lists
less_tail.next = greater_dummy.next
greater_tail.next = None  # CRITICAL: prevent cycles

return less_dummy.next

The dummy nodes eliminate all edge cases — you never need to check if a list is empty before appending.

The ListNode Class

class ListNode:
    """Standard singly linked list node."""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        parts = []
        node = self
        seen = set()
        while node and id(node) not in seen:
            seen.add(id(node))
            parts.append(str(node.val))
            node = node.next
        return " → ".join(parts)


def build_list(values):
    """Build a linked list from a Python list."""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

Problem 1: Partition List (LeetCode 86)

Problem: Given 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. Preserve the original relative order within each group.

Example:

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

Nodes with value < 3 are [1, 2, 2] and nodes with value >= 3 are [4, 3, 5]. Their relative order is preserved.

Solution

def partition(head, x):
    """
    Partition list around value x.
    Nodes with val < x come before nodes with val >= x.
    Preserves relative order within each group.
    
    LeetCode 86 — Partition List
    Time: O(n), Space: O(1)
    """
    # Create two dummy-headed lists
    less_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    less_tail = less_dummy
    greater_tail = greater_dummy

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

    # Connect the two lists
    less_tail.next = greater_dummy.next
    greater_tail.next = None  # Prevent cycle!

    return less_dummy.next


# Test
head = build_list([1, 4, 3, 2, 5, 2])
print("Before:", head)        # 1 → 4 → 3 → 2 → 5 → 2
result = partition(head, 3)
print("After: ", result)      # 1 → 2 → 2 → 4 → 3 → 5

Why greater_tail.next = None Is Critical

Without this line, the last node in the greater list still has its old next pointer, which might point to a node in the less list. This creates a cycle, causing infinite loops in any traversal.

Trace Through

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

Node 1 (1 < 3): less  = [1]
Node 4 (4 >= 3): greater = [4]
Node 3 (3 >= 3): greater = [4, 3]
Node 2 (2 < 3): less  = [1, 2]
Node 5 (5 >= 3): greater = [4, 3, 5]
Node 2 (2 < 3): less  = [1, 2, 2]

Join: 1 → 2 → 2 → 4 → 3 → 5
Set 5.next = None

Problem 2: Odd-Even Linked List (LeetCode 328)

Problem: Group all odd-indexed nodes together followed by all even-indexed nodes. The first node is considered odd (index 1), the second is even (index 2), and so on.

Example:

Input:  1 → 2 → 3 → 4 → 5
Output: 1 → 3 → 5 → 2 → 4

Odd positions: 1, 3, 5. Even positions: 2, 4.

Solution

def odd_even_list(head):
    """
    Group odd-indexed nodes before even-indexed nodes.
    Index starts at 1.
    
    LeetCode 328 — Odd Even Linked List
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return head

    odd = head          # First node (odd index 1)
    even = head.next    # Second node (even index 2)
    even_head = even    # Save for later connection

    while even and even.next:
        odd.next = even.next     # Skip even node
        odd = odd.next           # Advance odd pointer
        even.next = odd.next     # Skip odd node
        even = even.next         # Advance even pointer

    # Connect odd tail to even head
    odd.next = even_head

    return head


# Test
head = build_list([1, 2, 3, 4, 5])
print("Before:", head)           # 1 → 2 → 3 → 4 → 5
result = odd_even_list(head)
print("After: ", result)         # 1 → 3 → 5 → 2 → 4

head = build_list([2, 1, 3, 5, 6, 4, 7])
print("Before:", head)           # 2 → 1 → 3 → 5 → 6 → 4 → 7
result = odd_even_list(head)
print("After: ", result)         # 2 → 3 → 6 → 7 → 1 → 5 → 4

Trace Through

List: 1 → 2 → 3 → 4 → 5
odd = 1, even = 2, even_head = 2

Iteration 1:
  odd.next = 3 (skip 2), odd = 3
  even.next = 4 (skip 3), even = 4

Iteration 2:
  odd.next = 5 (skip 4), odd = 5
  even.next = None (skip 5), even = None

Loop ends. Connect: 5.next = 2 (even_head)
Result: 1 → 3 → 5 → 2 → 4

Why This Works Without Dummy Nodes

Unlike the partition problem, here we know exactly where odd and even nodes start (index 1 and 2). We do not need dummies because we always have a valid starting point.

Problem 3: Segregate 0s, 1s, and 2s

Problem: Given a linked list containing only 0s, 1s, and 2s, sort it in place without changing node values.

This is the Dutch National Flag problem adapted for linked lists. Instead of three-way swapping (as in arrays), we use the three-list-then-join technique.

Solution

def segregate_012(head):
    """
    Sort a linked list containing only 0s, 1s, and 2s.
    Rearranges nodes (not values).
    
    Time: O(n), Space: O(1)
    """
    # Three dummy-headed lists
    zero_dummy = ListNode(0)
    one_dummy = ListNode(0)
    two_dummy = ListNode(0)
    zero_tail = zero_dummy
    one_tail = one_dummy
    two_tail = two_dummy

    current = head
    while current:
        if current.val == 0:
            zero_tail.next = current
            zero_tail = current
        elif current.val == 1:
            one_tail.next = current
            one_tail = current
        else:
            two_tail.next = current
            two_tail = current
        current = current.next

    # Connect the three lists
    # Handle case where some groups might be empty
    if one_dummy.next:
        zero_tail.next = one_dummy.next
        one_tail.next = two_dummy.next
    else:
        zero_tail.next = two_dummy.next

    two_tail.next = None  # Prevent cycle

    # Return the first non-empty list
    if zero_dummy.next:
        return zero_dummy.next
    elif one_dummy.next:
        return one_dummy.next
    else:
        return two_dummy.next


# Test
head = build_list([1, 2, 0, 1, 2, 0, 1])
print("Before:", head)           # 1 → 2 → 0 → 1 → 2 → 0 → 1
result = segregate_012(head)
print("After: ", result)         # 0 → 0 → 1 → 1 → 1 → 2 → 2

head = build_list([2, 2, 1, 0])
print("Before:", head)           # 2 → 2 → 1 → 0
result = segregate_012(head)
print("After: ", result)         # 0 → 1 → 2 → 2

Simplified Connection Logic

The connection logic above handles empty groups, but we can simplify it:

def segregate_012_simple(head):
    """
    Simplified version with cleaner connection logic.
    Time: O(n), Space: O(1)
    """
    zero_d = ListNode(0)
    one_d = ListNode(0)
    two_d = ListNode(0)
    z, o, t = zero_d, one_d, two_d

    current = head
    while current:
        if current.val == 0:
            z.next = current
            z = current
        elif current.val == 1:
            o.next = current
            o = current
        else:
            t.next = current
            t = current
        current = current.next

    # Chain: zeros → ones → twos
    # If ones exist, zeros connect to ones; otherwise to twos
    z.next = one_d.next if one_d.next else two_d.next
    o.next = two_d.next
    t.next = None

    return zero_d.next or one_d.next or two_d.next

Generalizing: K-Way Partition

The two-list and three-list patterns generalize to K groups:

def partition_k_groups(head, k, classify_fn):
    """
    Partition a linked list into k groups based on classify_fn.
    classify_fn(node) should return an integer in [0, k-1].
    
    Time: O(n), Space: O(k) for dummy nodes
    """
    # Create k dummy-headed lists
    dummies = [ListNode(0) for _ in range(k)]
    tails = list(dummies)  # Copy references

    current = head
    while current:
        group = classify_fn(current)
        tails[group].next = current
        tails[group] = current
        current = current.next

    # Connect non-empty groups in order
    result_dummy = ListNode(0)
    result_tail = result_dummy
    for i in range(k):
        if dummies[i].next:
            result_tail.next = dummies[i].next
            result_tail = tails[i]

    result_tail.next = None
    return result_dummy.next


# Example: partition by value mod 3
head = build_list([5, 3, 8, 1, 6, 2, 7, 4])
result = partition_k_groups(head, 3, lambda node: node.val % 3)
print("Mod 3 groups:", result)
# Group 0 (mod 3 == 0): 3, 6
# Group 1 (mod 3 == 1): 1, 7, 4
# Group 2 (mod 3 == 2): 5, 8, 2
# Result: 3 → 6 → 1 → 7 → 4 → 5 → 8 → 2

Partition with Value Swapping (Alternative)

Sometimes you are allowed to swap values instead of rearranging nodes. This is simpler but not always acceptable in interviews:

def partition_by_swapping(head, x):
    """
    Partition by swapping values (not node pointers).
    Simpler but changes node values.
    Time: O(n), Space: O(1)
    """
    # Collect values, partition like an array
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next

    # Two-pointer partition on the array
    less = [v for v in values if v < x]
    greater_eq = [v for v in values if v >= x]
    sorted_vals = less + greater_eq

    # Write back
    current = head
    for val in sorted_vals:
        current.val = val
        current = current.next

    return head

Warning: This approach uses O(n) space and modifies node values. Most interviewers want the in-place pointer manipulation version.

Complexity Comparison

Problem	Time	Space	Technique
Partition around x	O(n)	O(1)	Two dummy lists
Odd-even grouping	O(n)	O(1)	Two pointers
Segregate 0s/1s/2s	O(n)	O(1)	Three dummy lists
K-way partition	O(n)	O(k)	K dummy lists
Value swapping	O(n)	O(n)	Array partition

All pointer-based approaches use O(1) extra space because the dummy nodes are constant overhead — they do not grow with input size.

Common Mistakes

1. Forgetting to terminate the last group. The last tail in the chain must have next = None. Otherwise, its old pointer creates a cycle.

2. Losing the even-head reference. In odd-even problems, save even_head before you start modifying pointers. If you lose it, you cannot reconnect the halves.

3. Wrong loop condition. In odd-even, the loop should check even and even.next, not odd and odd.next. The even pointer is always ahead, so it hits None first.

4. Empty group handling in 3-way partition. If all nodes are 2s, the zeros and ones lists are empty. Your connection logic must handle this gracefully.

Edge Cases to Test

# All same values
head = build_list([3, 3, 3])
print(partition(head, 3))      # 3 → 3 → 3 (all in "greater" group)

# All less than x
head = build_list([1, 1, 1])
print(partition(head, 5))      # 1 → 1 → 1 (all in "less" group)

# Single node
head = build_list([1])
print(partition(head, 1))      # 1

# Empty list
print(partition(None, 3))      # None

# Already partitioned
head = build_list([1, 2, 4, 5])
print(partition(head, 3))      # 1 → 2 → 4 → 5 (unchanged)

Practice Problems

1. LeetCode 86 — Partition List: Core partition problem (Medium)
2. LeetCode 328 — Odd Even Linked List: Index-based grouping (Medium)
3. GeeksforGeeks — Segregate 0s, 1s, and 2s: Three-way partition (Medium)
4. LeetCode 725 — Split Linked List in Parts: Divide into k roughly equal parts (Medium)
5. LeetCode 2161 — Partition Array According to Given Pivot: Array version of partition (Medium)
6. LeetCode 61 — Rotate List: Requires finding the split point, similar to partitioning (Medium)

Key Takeaways

• The dummy-node + two-list pattern is the cleanest way to partition linked lists. It eliminates all edge cases related to empty groups.
• Always set the last tail’s next to None after connecting groups — otherwise you create cycles.
• The odd-even problem uses direct pointer manipulation instead of dummy nodes because the starting positions are known.
• Three-way partition (0s/1s/2s) extends naturally to K-way partition using K dummy lists.
• Interviewers prefer pointer rearrangement over value swapping — it shows you understand linked list fundamentals.