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:


Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5]
Example 2:
Input: head = [2,1], x = 2 Output: [1,2]
Constraints:
- The number of nodes in the list is in the range
[0, 200]
. -100 <= Node.val <= 100
-200 <= x <= 200
Partition List Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode beforeHead(0);
ListNode afterHead(0);
ListNode* before = &beforeHead;
ListNode* after = &afterHead;
for (; head; head = head->next)
if (head->val < x) {
before->next = head;
before = head;
} else {
after->next = head;
after = head;
}
after->next = nullptr;
before->next = afterHead.next;
return beforeHead.next;
};
};
Java
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode beforeHead = new ListNode(0);
ListNode afterHead = new ListNode(0);
ListNode before = beforeHead;
ListNode after = afterHead;
for (; head != null; head = head.next)
if (head.val < x) {
before.next = head;
before = head;
} else {
after.next = head;
after = head;
}
after.next = null;
before.next = afterHead.next;
return beforeHead.next;
}
}
Python
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
beforeHead = ListNode(0)
afterHead = ListNode(0)
before = beforeHead
after = afterHead
while head:
if head.val < x:
before.next = head
before = head
else:
after.next = head
after = head
head = head.next
after.next = None
before.next = afterHead.next
return beforeHead.next
Watch Tutorial
Checkout more Solutions here