Problem
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.
Example:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
Solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function(head, x) {
var l1 = new ListNode(0);
var l2 = new ListNode(0);
var now1 = l1;
var now2 = l2;
var now = head;
while (now) {
if (now.val < x) {
now1.next = now;
now1 = now1.next;
} else {
now2.next = now;
now2 = now2.next;
}
now = now.next;
}
now1.next = l2.next;
now2.next = null;
return l1.next;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).