Skip to main content

86 - Partition List

Difficulty: Medium | Pattern: Linked List Manipulation | Company tags: Amazon, Microsoft

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.

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]

Approach: Two-Pointer Dummy Nodes — O(n), O(1)​

Key insight: Create two separate lists — one for nodes less than x, one for nodes >= x. Walk the original list once, routing each node to the appropriate list. Then join the two lists.

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

def partition(head, x: int):
    less_dummy = ListNode(0)
    greater_dummy = ListNode(0)
    less = less_dummy
    greater = greater_dummy
    
    curr = head
    while curr:
        if curr.val < x:
            less.next = curr
            less = less.next
        else:
            greater.next = curr
            greater = greater.next
        curr = curr.next
    
    greater.next = None      # terminate the greater list
    less.next = greater_dummy.next  # connect the two lists
    
    return less_dummy.next

Algorithm Flow​

Dry Run​

head = [1,4,3,2,5,2], x = 3

Nodeval lt 3?less listgreater list
1Yes (1 lt 3)[1][]
4No (4 gte 3)[1][4]
3No (3 gte 3)[1][4,3]
2Yes (2 lt 3)[1,2][4,3]
5No (5 gte 3)[1,2][4,3,5]
2Yes (2 lt 3)[1,2,2][4,3,5]

Connect: [1,2,2] → [4,3,5] → Output: [1,2,2,4,3,5] ✓

Common Mistake​

Forgetting greater.next = None. After rerouting nodes, the last node in the greater list may still point to some node in the original list, creating a cycle or incorrect tail. Always terminate.

Edge Cases​

  • All nodes less than x → greater list empty, returns less list
  • All nodes >= x → less list empty, returns greater list
  • Empty list → returns None
  • Single node → returned as-is in the appropriate partition

Complexity​

  • Time: O(n) — single pass through the list
  • Space: O(1) — only rearranging existing nodes, no new allocations (dummy nodes are constant)

Key Terms​

TermDefinition
Dummy nodeA placeholder head node used to simplify edge cases when building or modifying a linked list.
Two-pointer / two-list techniqueMaintaining separate tail pointers for two sub-lists being built simultaneously in a single pass.
Stable partitioningRearranging elements into groups while preserving the original relative order within each group.
List splicingJoining two linked lists together by pointing one list's tail next to the other list's head.
In-place rearrangementModifying node pointers directly instead of allocating new nodes, achieving O(1) extra space.

FAQ​

Q: Can this be solved without extra dummy nodes? A: You could track raw head/tail pointers for each partition and handle the "first node" case with conditionals, but dummy nodes remove that special-casing and make the code cleaner — they don't add real extra space (O(1)).

Q: What if the list is empty? A: curr = head is None immediately, the while loop never executes, and less_dummy.next is None, so the function correctly returns None.

Q: How would this change if we needed to preserve order but partition into three groups (less, equal, greater)? A: Use three dummy/tail pointers instead of two (similar to the Dutch National Flag idea), routing each node based on comparison to x, then splice all three lists together at the end.

Q: What's the follow-up interviewers usually ask? A: "Can you do this without creating a cycle bug?" — prompting discussion of why greater.next = None is required to terminate the tail properly, since the last node in the greater list might still point to a node that got moved to the less list.

Q: Why must the relative order be preserved, and how does the algorithm guarantee it? A: The problem explicitly requires stability. Because the algorithm processes nodes strictly in their original order and appends each to the tail of its partition's list, both partitions naturally retain their original relative ordering.

Quick Revision​

  • Build two separate linked lists in one pass: less (val < x) and greater (val >= x).
  • Use dummy head nodes for both lists to avoid special-casing the first node.
  • Route each node to the appropriate list's tail as you walk the original list.
  • After the loop, terminate the greater list with greater.next = None to avoid cycles.
  • Splice the two lists: less.next = greater_dummy.next.
  • Return less_dummy.next as the new head.
  • Time: O(n) single pass; Space: O(1), only pointers are rearranged, no new nodes allocated.
  • Edge cases: empty list, all nodes on one side, single-node list.
  • Common bug: forgetting to null-terminate the greater list's tail.