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.
 

Example

Given 1->4->3->2->5->2->null and x = 3,
return 1->2->2->4->3->5->null.

I like the algorithm to this problem. Much much better than my original thought of using swapping. I makes two list and join them at the end. The logic is very clear under help of dummy headers. Smart!

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @param x: an integer * @return: a ListNode */ public ListNode partition(ListNode head, int x) { // write your code here if (head == null) { return null; } //this is very goood algorthm: making two seperate list and join them at last //no swapping required //we need enough pointer to not lose any nodes ListNode leftDummyH = new ListNode(0); ListNode rightDummyH = new ListNode(0); ListNode left = leftDummyH, right = rightDummyH; //keep proceeding head while (head != null) {//O(n) //left points to node value less than x if (head.val < x) { left.next = head; left = left.next; } else {//other wise, it belogs to right list right.next = head; right = right.next; } head = head.next; } right.next = null;//close right left.next = rightDummyH.next;//join right with left return leftDummyH.next;///return left head } }