Log inSign up
mediumLeetCodeNot Started

Partition List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

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.

Example 1 · Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]
Explanation: Nodes less than 3 are 1, 2, 2. Nodes >= 3 are 4, 3, 5. Spliced together preserving relative order: [1, 2, 2, 4, 3, 5].

Example 2 · Example 2:

Input: head = [2,1], x = 2
Output: [1,2]
Explanation: Node 1 is less than 2, node 2 is >= 2. Output is [1, 2].

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement stable two-way linked list partitioning using dual sentinel nodes.
  • Prevent pointer cycle formation by explicitly nullifying partition tails.
  • Preserve relative chronological order without auxiliary memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Stable partitioning of elements based on a threshold pivot x.
  • Preserving relative insertion order in both partitions.
  • O(1) memory requirement.

Algorithmic Decision Tree:

  • Use two sentinel dummy heads lessDummy and greaterDummy to handle empty partitions seamlessly.
  • Always set greaterTail.next = null before returning to avoid circular pointer loops.

Connected Patterns:

Odd Even Linked ListQuicksort PartitioningSort List

1. Brute Force — Array Storage & Value Overwrite

Intuition

Read all node values into two separate arrays: < x and >= x. Combine the arrays and overwrite node values.

Algorithm

  1. Step 1: Traverse list, adding values < x to less, and >= x to greater.
  2. Step 2: Combine combined = less + greater.
  3. Step 3: Traverse list again, setting curr.val = combined[i].
  4. Step 4: Return head.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode* partition(ListNode* head, int x) {
15 if (!head || !head->next) return head;
16 vector<int> less, greater;
17 for (ListNode* c = head; c; c = c->next) {
18 if (c->val < x) less.push_back(c->val);
19 else greater.push_back(c->val);
20 }
21
22 ListNode* curr = head;
23 for (int v : less) { curr->val = v; curr = curr->next; }
24 for (int v : greater) { curr->val = v; curr = curr->next; }
25 return head;
26 }
27};
28
29int main() {
30 ListNode* h = new ListNode(1);
31 h->next = new ListNode(4);
32 h->next->next = new ListNode(3);
33 h->next->next->next = new ListNode(2);
34 h->next->next->next->next = new ListNode(5);
35 h->next->next->next->next->next = new ListNode(2);
36
37 Solution sol;
38 ListNode* res = sol.partition(h, 3);
39
40 cout << "Brute Force Partition: ";
41 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
42 cout << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N) — Extracts N values in O(N), partitions in O(N), writes back in O(N).
  • Space complexity: O(N) — Allocates array buffer of size N.

Why Brute Force Doesn't Scale:

Array allocations violate the O(1) space requirement and duplicate node values.

For N = 100,000 nodes, dual sentinel partitioning executes in <1ms with 0 heap bytes allocated.

2. Better — Single-Chain In-Place Node Splicing

Intuition

Use a dummy head. Maintain lessTail pointing to the last node known to be < x. As we encounter downstream nodes < x, detach them from their current position and insert them right after lessTail.

Algorithm

  1. Step 1: Create dummy = new ListNode(0, head), lessTail = dummy, prev = dummy, curr = head.
  2. Step 2: Find first node >= x; while curr && curr.val < x, lessTail = curr, prev = curr, curr = curr.next.
  3. Step 3: While curr != null:
  4. a. If curr.val < x: detach curr (prev.next = curr.next), insert after lessTail (curr.next = lessTail.next, lessTail.next = curr, lessTail = curr), advance curr = prev.next.
  5. b. Else: prev = curr, curr = curr.next.
  6. Step 4: Return dummy.next.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9 ListNode(int x, ListNode* n) : val(x), next(n) {}
10};
11
12class Solution {
13public:
14 ListNode* partition(ListNode* head, int x) {
15 if (!head || !head->next) return head;
16
17 ListNode dummy(0, head);
18 ListNode* lessTail = &dummy;
19 ListNode* prev = &dummy;
20 ListNode* curr = head;
21
22 while (curr && curr->val < x) {
23 lessTail = curr;
24 prev = curr;
25 curr = curr->next;
26 }
27
28 while (curr) {
29 if (curr->val < x) {
30 prev->next = curr->next;
31 curr->next = lessTail->next;
32 lessTail->next = curr;
33 lessTail = curr;
34 curr = prev->next;
35 } else {
36 prev = curr;
37 curr = curr->next;
38 }
39 }
40
41 return dummy.next;
42 }
43};
44
45int main() {
46 ListNode* h = new ListNode(1, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(5, new ListNode(2))))));
47
48 Solution sol;
49 ListNode* res = sol.partition(h, 3);
50
51 cout << "Better In-Place Partition: ";
52 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
53 cout << endl;
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(N) — Traverses the list once in O(N) time.
  • Space complexity: O(1) — Operates strictly in-place with a single dummy head.

3. Optimal — Dual Dummy Sentinel Lists (less & greater)

Intuition

Create two dummy sentinel nodes: beforeHead (for elements < x) and afterHead (for elements >= x). Iterate through the input list, appending each node to beforeTail or afterTail. When done, set afterTail.next = null (to cut off cycles) and beforeTail.next = afterHead.next.

Algorithm

  1. Step 1: Create beforeDummy = new ListNode(0), afterDummy = new ListNode(0).
  2. Step 2: Initialize before = beforeDummy, after = afterDummy, curr = head.
  3. Step 3: While curr != null:
  4. a. If curr.val < x: before.next = curr, before = before.next.
  5. b. Else: after.next = curr, after = after.next.
  6. c. curr = curr.next.
  7. Step 4: Set after.next = null (crucial: avoids forming a cycle with downstream nodes).
  8. Step 5: Set before.next = afterDummy.next.
  9. Step 6: Return beforeDummy.next.

Partition List Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Iterating through list
Visual state
Values and pointers at this exact step
linked list
before → beforeDummyafter → afterDummy
Node 1
1
Node 4
4
Node 3
3
Node 2a
2
Node 5
5
Node 2b
2
NULL
Check / comparison
Scan started
Decision / next transition
Distribute nodes
Why this step matters

Iterating through list.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode* partition(ListNode* head, int x) {
14 ListNode beforeDummy(0);
15 ListNode afterDummy(0);
16 ListNode* before = &beforeDummy;
17 ListNode* after = &afterDummy;
18 ListNode* curr = head;
19
20 while (curr) {
21 if (curr->val < x) {
22 before->next = curr;
23 before = before->next;
24 } else {
25 after->next = curr;
26 after = after->next;
27 }
28 curr = curr->next;
29 }
30
31 after->next = nullptr;
32 before->next = afterDummy.next;
33 return beforeDummy.next;
34 }
35};
36
37int main() {
38 ListNode* h = new ListNode(1);
39 h->next = new ListNode(4);
40 h->next->next = new ListNode(3);
41 h->next->next->next = new ListNode(2);
42 h->next->next->next->next = new ListNode(5);
43 h->next->next->next->next->next = new ListNode(2);
44
45 Solution sol;
46 ListNode* res = sol.partition(h, 3);
47
48 cout << "Optimal Partition: ";
49 for (ListNode* c = res; c; c = c->next) cout << c->val << (c->next ? " -> " : "");
50 cout << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N) — Visits each of the N nodes exactly once in a single forward pass. O(N) linear time.
  • Space complexity: O(1) — Uses 2 stack-allocated dummy nodes and pointers requiring strictly O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Array Partition & Value OverwritingO(N)O(N)Traverse the list and store values < x in array less and values >= x in array greater. Combine them and overwrite the original list's node values.Memory allocation.
2.Better — Single-List In-Place Splicing & InsertionO(N)O(1)Traverse with a dummy head. Whenever a node < x is found downstream, excise it from its current position and insert it right after the last placed < x node.Complex pointer surgery.
3.Optimal — Two Dummy Sentinel Lists (less & greater)OptimalO(N)O(1)Maintain lessDummy and greaterDummy. Append each node to lessTail or greaterTail. Set greaterTail.next = null and lessTail.next = greaterDummy.next.Optimal.

Common Pitfalls & Crucial Edge Cases

Forgetting `after.next = null`

If the last node in after previously pointed to a node that went into before, failing to nullify after.next creates an infinite cycle.

Sorting values inside partitions

The problem requires preserving the original relative order, NOT sorting values within each partition.

Creating new nodes

Allocating new node objects instead of rewiring existing pointer targets wastes memory.

Crucial Edge Cases to Validate:

  • Empty List — head = null -> returns null.
  • All Elements < x — head = [1, 2], x = 5 -> afterDummy.next is null, before.next = null -> returns [1, 2].
  • All Elements >= x — head = [5, 6], x = 2 -> beforeDummy.next is null, before.next = afterDummy.next -> returns [5, 6].
  • Single Element — head = [1], x = 0 -> returns [1].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the dual dummy sentinel design immediately: 'We create beforeHead and afterHead dummy sentinels.'
  2. Explicitly emphasize the crucial trap: 'after.next = null is mandatory to break potential cyclic dependencies.'
  3. Mention how this preserves stability in strict O(N) time and O(1) space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is after.next = null critical at the end of the partition algorithm?

2.What is the time and space complexity of the dual sentinel approach?

3.Does this partition algorithm maintain stable relative ordering?

Back to DSA Sheet