Partition List

Overview

Partition list means rearranging the list so that all nodes with value less than a given x come before nodes with value greater than or equal to x. Relative order of nodes in each part should be preserved. This is the same idea as the partition step in quicksort. Use two Dummy Head lists: one for "less than x" and one for "greater or equal"; traverse once, append each node to the appropriate list, then concatenate the two lists. O(n) time, O(1) space (only pointers).

Key idea: You don't need to swap in place. Build two separate chains (small and large), then small.next = largeHead and largeTail.next = null. A dummy for each chain avoids special cases for the first node.

When to Use

• Partition list — Exact problem (e.g. LeetCode Partition List).
• Quicksort on linked list — Partition by pivot, then recursively sort the two parts and concatenate.
• Dutch national flag style — If you had three groups, use three dummy lists.

How It Works

1. Create two dummies: smallDummy and largeDummy; smallTail = smallDummy, largeTail = largeDummy.
2. Traverse the list: for each node, if node.val < x append to small (smallTail.next = node, smallTail = node), else append to large (largeTail.next = node, largeTail = node).
3. Cut the list: set largeTail.next = null (important: the last node of the large list might still point to something in the original list).
4. Connect: smallTail.next = largeDummy.next.
5. Return smallDummy.next (if no small nodes, this is largeDummy.next; both dummies work).

Example 1: Partition List

Problem: Given the head of a linked list and a value x, partition it so that all nodes less than x come before nodes greater than or equal to x. Preserve the original relative order.

function partition(head: ListNode | null, x: number): ListNode | null {
  const smallDummy = new ListNode(-1);
  const largeDummy = new ListNode(-1);
  let smallTail = smallDummy;
  let largeTail = largeDummy;
  let curr: ListNode | null = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = null;
    if (curr.val < x) {
      smallTail.next = curr;
      smallTail = curr;
    } else {
      largeTail.next = curr;
      largeTail = curr;
    }
    curr = next;
  }
  largeTail.next = null;
  smallTail.next = largeDummy.next;
  return smallDummy.next;
}

• Time: O(n), Space: O(1).

Edge Cases

• All nodes < x — Large list is empty; smallTail.next = largeDummy.next is null; correct.
• All nodes >= x — Small list is empty; return smallDummy.next = largeDummy.next; correct.
• Empty list — Return null; smallDummy.next is never set, so return smallDummy.next is null if you don't attach large. Better: if head is null return null, or ensure smallTail.next = largeDummy.next and largeDummy.next is null.
• Single node — One list gets the node, the other stays empty; link and return.

Common Mistakes

1. Not breaking links — Set curr.next = null when appending to a list so you don't carry over old next pointers and create cycles or wrong order.
2. Forgetting largeTail.next = null — The last node in the large list might still point into the original list; clear it.
3. Return value — When all nodes are >= x, smallDummy.next is still null; connecting smallTail.next = largeDummy.next makes the full list start at largeDummy.next, but you return smallDummy.next which is still null unless you did smallTail.next = largeDummy.next. So after smallTail.next = largeDummy.next, smallDummy.next is the head of small list (or if small was empty, smallTail is smallDummy, so smallDummy.next = largeDummy.next). Correct.

Time and Space Complexity

• Time: O(n).
• Space: O(1).

Summary

• Partition list: Two dummies (small, large), one pass to append each node to the right list, then smallTail.next = largeHead, largeTail.next = null; return smallDummy.next.
• See Dummy Head. Related: Sort List (merge sort); partition is used in quicksort-style list sort.