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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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.