Start practising

Partition List

Medium Linked List Miscellaneous Original on LeetCode

Partition List is a medium linked list problem solved with the miscellaneous pattern. The best approach, optimal (two dummy lists), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from copy values into two arrays up.

Problem

Rearrange a linked list so every node with value less than x comes before every node with value at least x, keeping the original relative order inside each part.

Examples

Example 1

Input
head = [1, 4, 3, 2, 5, 2], x = 3
Output
[1, 2, 2, 4, 3, 5]
Why
Values below 3 first, in their original order, then the rest in order.

Example 2

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

Constraints

  • The list has 0 to 200 nodes.
  • Keep the original relative order within each part.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Copy values into two arraysO(n)O(n)
Optimal (two dummy lists)O(n)O(1)

1Copy values into two arrays

TimeO(n)
SpaceO(n)

Collect values below x and values at least x into two lists, then write them back in that order.

  1. Two passes over the list collecting values; one pass writing them back.
Java
class Solution {
    public ListNode partition(ListNode head, int x) {
        List<Integer> lo = new ArrayList<>(), hi = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) (p.val < x ? lo : hi).add(p.val);
        lo.addAll(hi);
        ListNode p = head;
        for (int v : lo) { p.val = v; p = p.next; }
        return head;
    }
}

2Optimal (two dummy lists)

TimeO(n)
SpaceO(1)

Move each node to the tail of the before list or the after list. Join before's tail to after's head, and end the after list with null so no old link creates a cycle.

  1. Two dummies with tails b and a.
  2. Append each node to b if val < x, else to a.
  3. a.next = null; b.next = afterDummy.next; return beforeDummy.next.
Java
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode beforeHead = new ListNode(), afterHead = new ListNode();
        ListNode b = beforeHead, a = afterHead;
        for (ListNode p = head; p != null; p = p.next) {
            if (p.val < x) { b.next = p; b = p; }
            else { a.next = p; a = p; }
        }
        a.next = null;
        b.next = afterHead.next;
        return beforeHead.next;
    }
}

Edge cases to test

  • All values below x, or none
  • Values equal to x go to the second part

Hints

Hint 1

Build two separate lists with two dummy heads, then join them.

FAQ

What is the best time complexity for Partition List?

Optimal (two dummy lists) runs in O(n) time and O(1) extra space.

Which pattern does Partition List use?

It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.

Is there a brute force solution for Partition List?

Yes. Copy values into two arrays takes O(n) time and O(n) space. Collect values below x and values at least x into two lists, then write them back in that order.

Which edge cases should I test for Partition List?

All values below x, or none; Values equal to x go to the second part.