Question
Given 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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Stats
| Frequency | 3 |
| Difficulty | 3 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This question is not very difficult, but can be confusing if the code don’t have good logic.
Solution
There is no fancy algorithm solution. I got it wrong in 10 submissions at first. After a few days, I did this problem again and passed with 1 attempt.
So just keep practicing.
Code
my code
public ListNode partition(ListNode head, int x) {
if (head == null) return head;
ListNode PH = new ListNode(1);
PH.next = head;
ListNode left = PH, preRight = PH, right = head;
while (right != null) {
if (right.val < x) {
if (preRight != left) {
preRight.next = right.next;
right.next = left.next;
left.next = right;
left = right;
right = preRight.next;
} else {
left = left.next;
preRight = left;
right = right.next;
}
} else {
preRight = right;
right = preRight.next;
}
}
return PH.next;
}