🧠
Better Approach (Two Linked Lists with Dummy Heads)
💡 This approach improves space by using linked lists directly instead of arrays, preserving order and avoiding extra memory for values.
Intuition
Create two separate linked lists: one for nodes less than x and one for nodes greater or equal to x, then connect them at the end.
Algorithm
- Initialize two dummy nodes: lessHead and greaterHead.
- Traverse the original list, appending nodes to less or greater list based on their value.
- Connect the less list's tail to the head of the greater list.
- Set the greater list's tail next pointer to null and return lessHead.next.
💡 This approach requires careful pointer manipulation but is efficient and preserves order without extra space for values.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def partition(head, x):
less_head = ListNode(0)
greater_head = ListNode(0)
less = less_head
greater = greater_head
current = head
while current:
if current.val < x:
less.next = current
less = less.next
else:
greater.next = current
greater = greater.next
current = current.next
greater.next = None
less.next = greater_head.next
return less_head.next
# Driver code
if __name__ == '__main__':
nodes = [1,4,3,2,5,2]
dummy = ListNode(0)
curr = dummy
for v in nodes:
curr.next = ListNode(v)
curr = curr.next
new_head = partition(dummy.next, 3)
curr = new_head
res = []
while curr:
res.append(curr.val)
curr = curr.next
print(res) # Expected: [1,2,2,4,3,5]
Line Notes
less_head = ListNode(0)Dummy node to start less-than-x list
greater_head = ListNode(0)Dummy node to start greater-or-equal list
while current:Traverse original list once
if current.val < x:Append node to less list preserving order
greater.next = NoneTerminate greater list to avoid cycles
less.next = greater_head.nextConnect less list to greater list
return less_head.nextReturn head of the combined partitioned list
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; this.next = null; }
}
public class Solution {
public ListNode partition(ListNode head, int x) {
ListNode lessHead = new ListNode(0);
ListNode greaterHead = new ListNode(0);
ListNode less = lessHead, greater = greaterHead;
ListNode current = head;
while (current != null) {
if (current.val < x) {
less.next = current;
less = less.next;
} else {
greater.next = current;
greater = greater.next;
}
current = current.next;
}
greater.next = null;
less.next = greaterHead.next;
return lessHead.next;
}
public static void main(String[] args) {
int[] nodes = {1,4,3,2,5,2};
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
for (int v : nodes) {
curr.next = new ListNode(v);
curr = curr.next;
}
Solution sol = new Solution();
ListNode newHead = sol.partition(dummy.next, 3);
curr = newHead;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println(); // Expected: 1 2 2 4 3 5
}
}
Line Notes
ListNode lessHead = new ListNode(0);Dummy node for less partition
ListNode greaterHead = new ListNode(0);Dummy node for greater partition
while (current != null)Single pass traversal of original list
if (current.val < x)Append node to less list preserving order
greater.next = null;Terminate greater list to prevent cycles
less.next = greaterHead.next;Connect less list to greater list
return lessHead.next;Return combined partitioned list head
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode lessHead(0), greaterHead(0);
ListNode* less = &lessHead;
ListNode* greater = &greaterHead;
ListNode* current = head;
while (current) {
if (current->val < x) {
less->next = current;
less = less->next;
} else {
greater->next = current;
greater = greater->next;
}
current = current->next;
}
greater->next = nullptr;
less->next = greaterHead.next;
return lessHead.next;
}
};
int main() {
int nodes[] = {1,4,3,2,5,2};
ListNode dummy(0);
ListNode* curr = &dummy;
for (int v : nodes) {
curr->next = new ListNode(v);
curr = curr->next;
}
Solution sol;
ListNode* newHead = sol.partition(dummy.next, 3);
curr = newHead;
while (curr) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl; // Expected: 1 2 2 4 3 5
return 0;
}
Line Notes
ListNode lessHead(0), greaterHead(0);Dummy nodes to start partitions
while (current)Traverse original list once
if (current->val < x)Append node to less partition preserving order
greater->next = nullptr;Terminate greater list to avoid cycles
less->next = greaterHead.next;Connect less and greater partitions
return lessHead.next;Return head of combined partitioned list
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
function partition(head, x) {
const lessHead = new ListNode(0);
const greaterHead = new ListNode(0);
let less = lessHead;
let greater = greaterHead;
let current = head;
while (current !== null) {
if (current.val < x) {
less.next = current;
less = less.next;
} else {
greater.next = current;
greater = greater.next;
}
current = current.next;
}
greater.next = null;
less.next = greaterHead.next;
return lessHead.next;
}
// Driver code
const nodes = [1,4,3,2,5,2];
const dummy = new ListNode(0);
let curr = dummy;
nodes.forEach(v => {
curr.next = new ListNode(v);
curr = curr.next;
});
const newHead = partition(dummy.next, 3);
let res = [];
curr = newHead;
while (curr !== null) {
res.push(curr.val);
curr = curr.next;
}
console.log(res); // Expected: [1,2,2,4,3,5]
Line Notes
const lessHead = new ListNode(0);Dummy node for less partition
const greaterHead = new ListNode(0);Dummy node for greater partition
while (current !== null)Traverse original list once
if (current.val < x)Append node to less partition preserving order
greater.next = null;Terminate greater list to avoid cycles
less.next = greaterHead.next;Connect less and greater partitions
return lessHead.next;Return head of combined partitioned list
Single pass through the list (O(n)) and only constant extra space for dummy nodes and pointers.
💡 For n=100,000 nodes, this means about 100,000 operations and minimal extra memory, making it efficient and scalable.
Interview Verdict: Accepted and optimal in time and space
This is the preferred approach in interviews because it is efficient and uses constant extra space.