Partition List
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.
Method:
Create two dummy nodes to keep track of the smaller elements and bigger elements.
Solution:
Time: O(n)
Space: O(1)
/**
* Definition for singly-linked list.
* class ListNode {
* public int val;
* public ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
public ListNode partition(ListNode A, int B) {
ListNode dummySmaller = new ListNode(0);
ListNode dummyBiggerOrEqual = new ListNode(0);
ListNode pSE = dummySmaller;
ListNode pB = dummyBiggerOrEqual;
ListNode curr = A;
while (curr != null) {
ListNode next = curr.next;
if (curr.val < B) {
pSE.next = curr;
pSE = pSE.next;
} else {
pB.next = curr;
pB = pB.next;
}
curr = next;
}
pB.next = null;
pSE.next = dummyBiggerOrEqual.next;
return dummySmaller.next;
}
}