Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Partition List

Partition List

Master this topic with zero to advance depth.

Partition List

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. You should preserve the original relative order of the nodes in each of the two partitions.

Visual Representation

List: 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3 Step 1: Create two lists: Small and Large. Step 2: Traverse and assign: Small: 1 -> 2 -> 2 Large: 4 -> 3 -> 5 Step 3: Connect Small.next to Large.next. Result: 1 -> 2 -> 2 -> 4 -> 3 -> 5
Medium

Examples

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Nodes less than 3 are 1, 2, 2. Nodes >= 3 are 4, 3, 5. Order is preserved.

Approach 1

Level I: Brute Force (Extra Space)

Intuition

Iterate through the list twice (or once with two collections). In the first pass, collect all nodes smaller than x. In the second pass, collect all nodes greater than or equal to x. Finally, rebuild the list.

Visual Trace

List: 1 -> 4 -> 3 -> 2, x=3 Pass 1 (<3): [1, 2] Pass 2 (>=3): [4, 3] Combined: [1, 2, 4, 3] New List: 1 -> 2 -> 4 -> 3

Iterate and store values in two separate lists (or an array). Traverse the stored values to create a new linked list.

⏱ O(N)💾 O(N)

Detailed Dry Run

Input: [1, 4, 3, 2], x=3 Lists: Small=[1, 2], Large=[4, 3]. Rebuild: 1->2->4->3.

java
public ListNode partition(ListNode head, int x) {
    List<Integer> small = new ArrayList<>(), large = new ArrayList<>();
    ListNode curr = head;
    while (curr != null) {
        if (curr.val < x) small.add(curr.val);
        else large.add(curr.val);
        curr = curr.next;
    }
    ListNode dummy = new ListNode(0), res = dummy;
    for (int v : small) { res.next = new ListNode(v); res = res.next; }
    for (int v : large) { res.next = new ListNode(v); res = res.next; }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

O(N) space is not ideal. Rebuilding the list creates new node objects.

Approach 2

Level II: In-place Node Movement

Intuition

If we don't care about relative order, we could swap values. Since we must preserve it, this approach involves detaching nodes >= x and appending them to a secondary 'large' list, while keeping < x nodes in the 'small' list.

Visual Trace

List: 1 -> 4 -> 3 -> 2, x=3 Small Head: [DummyS] Large Head: [DummyL] Node 1: <3, DummyS -> 1 Node 4: >=3, DummyL -> 4 Node 3: >=3, DummyL -> 4 -> 3 Node 2: <3, DummyS -> 1 -> 2 Connect: DummyS -> 1 -> 2 -> 4 -> 3

Iterate through the list. If a node is >= x, move it to a temporary 'large' list. If < x, keep it in the 'small' list. This is similar to Level III but implemented strictly with node movement.

⏱ O(N)💾 O(1)

Detailed Dry Run

Identical to Level III intuition but focused on pointer manipulation without separate head nodes.

java
public ListNode partition(ListNode head, int x) {
    ListNode dummy = new ListNode(0, head), prev = dummy, curr = head;
    ListNode tailHead = new ListNode(0), tail = tailHead;
    while (curr != null) {
        if (curr.val >= x) {
            prev.next = curr.next;
            tail.next = curr;
            tail = tail.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    tail.next = null;
    prev.next = tailHead.next;
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

Strict pointer management is required to avoid cycles or losing nodes.

Approach 3

Level III: Optimal (Two Pointer - Separate Lists)

Intuition

The simplest way to maintain relative order is to create two separate lists: one for nodes smaller than x and another for nodes greater than or equal to x. Finally, link the end of the first list to the head of the second list.

⏱ O(N)💾 O(1) (new nodes are just pointers to existing ones)

Detailed Dry Run

Input: 1->4->3->2, x=3

  • 1 < 3: Small: 1
  • 4 >= 3: Large: 4
  • 3 >= 3: Large: 4->3
  • 2 < 3: Small: 1->2
  • End: Connect 1->2 to 4->3 -> 1->2->4->3
java
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode beforeHead = new ListNode(0);
        ListNode afterHead = new ListNode(0);
        ListNode before = beforeHead, after = afterHead;
        while (head != null) {
            if (head.val < x) {
                before.next = head;
                before = before.next;
            } else {
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;
        before.next = afterHead.next;
        return beforeHead.next;
    }
}

⚠️ Common Pitfalls & Tips

Remember to set after.next = null to avoid cycles in the list.

← Previous QuestionRemove Nth Node From End of List
Next Question →Merge K Sorted Lists