Partition List

Medium
2006.

Partition List

Partition List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Adobe and Bloomberg interviews.

Given the head of a singly linked list and a value x, rearrange the list so that every node with a value less than x comes before every node with a value greater than or equal to x.

Keep the original relative order of the nodes inside each of the two groups, and return the head of the rearranged list.

Example 1

Input
head = [1,4,3,2,5,2], x = 3
Output
[1,2,2,4,3,5]
Explanation
Smaller than 3: 1, 2, 2 (in their order); the rest: 4, 3, 5.

Example 2

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

Example 3

Input
head = [], x = 0
Output
[]

Constraints

  • The number of nodes in the list is in the range [0, 200]
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Partition List — Solution in Python, Java & C++

Partition List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on two pointers.

Partition List is a medium coding problem on two pointers, asked in Amazon, Microsoft, Adobe and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Two Pointers
  • Asked at: Amazon, Microsoft, Adobe, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the head of a singly linked list and a value x, rearrange the list so that every node with a value less than x comes before every node with a value greater than or equal to x.

Keep the original relative order of the nodes inside each of the two groups, and return the head of the rearranged list.

Example 1

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: Smaller than 3: 1, 2, 2 (in their order); the rest: 4, 3, 5.

Example 2

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

Example 3

Input: head = [], x = 0
Output: []

Constraints

  • The number of nodes in the list is in the range [0, 200]
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

Hints for Partition List

  1. Hint 1

    The answer is a stable split: the small nodes in order, followed by the large nodes in order.

  2. Hint 2

    Build two separate lists while walking the original once — one for values < x, one for the rest.

  3. Hint 3

    Give each list a dummy head and a tail pointer; at the end link the small list's tail to the large list's head, and end the large list with null.

How to solve Partition List

Distribute the nodes into two chains as you meet them — values below x and the rest — then join the chains. Appending at a tail keeps each chain in its original order.

Approach

  1. Create dummy heads small and large with tails s and l.
  2. Walk the list; append each node to s if its value is < x, otherwise to l.
  3. Set l.next = null (the last large node may still point into the old list).
  4. Set s.next = large.next and return small.next.

Why it works

Each node is appended exactly once to the chain its value selects, and appending preserves the order of arrival, so each group keeps its relative order. Joining small before large puts every smaller value first.

Complexity

  • Time — O(n)
  • Space — O(1) — the nodes are relinked, not copied

Pitfalls

  • Forgetting l.next = null can leave a cycle back into the small chain.
  • Values equal to x belong to the second group.
  • Swapping values in place (like an array partition) breaks the required stable order.

Reference solution

Python

from typing import Optional

def partition(head: Optional[ListNode], x: int) -> Optional[ListNode]:
    small = ListNode(0)
    large = ListNode(0)
    s, l = small, large
    while head:
        if head.val < x:
            s.next = head
            s = head
        else:
            l.next = head
            l = head
        head = head.next
    l.next = None
    s.next = large.next
    return small.next

Java

public static ListNode partition(ListNode head, int x) {
    ListNode small = new ListNode(0), large = new ListNode(0), s = small, l = large;
    while (head != null) {
        if (head.val < x) { s.next = head; s = head; }
        else { l.next = head; l = head; }
        head = head.next;
    }
    l.next = null;
    s.next = large.next;
    return small.next;
}

C++

ListNode* partition(ListNode* head, int x) {
    ListNode small(0), large(0);
    ListNode *s = &small, *l = &large;
    while (head) {
        if (head->val < x) { s->next = head; s = head; }
        else { l->next = head; l = head; }
        head = head->next;
    }
    l->next = nullptr;
    s->next = large.next;
    return small.next;
}

JavaScript

var partition = function(head, x) {
    var small = new ListNode(0), large = new ListNode(0), s = small, l = large;
    while (head !== null) {
        if (head.val < x) { s.next = head; s = head; }
        else { l.next = head; l = head; }
        head = head.next;
    }
    l.next = null;
    s.next = large.next;
    return small.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 165 two pointers problems · the whole catalogue

Learn the technique: Two Pointers Technique