Partition List Visualizer & Step-by-Step Algorithm Solution

Partition a linked list such that all nodes less than x come before nodes greater than or equal to x, preserving relative order.

Category: linked-list | Difficulty: Medium

Tags: Linked List, Two Pointers, Partition

Partition List

head, curr
1
4
3
2
5
2
∅
100%
state
x3
curr.val1
curr.val < xtrue
t1.valN/A
t2.valN/A
Initial List
1/30
Explanation

Given linked list [1, 4, 3, 2, 5, 2] and partition value x = 3. Partition so all nodes < 3 appear before nodes >= 3.

Source Code
1function partition(head, x) {
2 if (!head || !head.next) return head;
3 const dummyLess = new ListNode(-1);
4 const dummyMore = new ListNode(-1);
5 let t1 = dummyLess;
6 let t2 = dummyMore;
7 let curr = head;
8 while (curr) {
9 if (curr.val < x) {
10 t1.next = curr;
11 t1 = curr;
12 } else {
13 t2.next = curr;
14 t2 = curr;
15 }
16 curr = curr.next;
17 }
18 t2.next = null;
19 t1.next = dummyMore.next;
20 return dummyLess.next;
21}