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->null
and x = 3,
return 1->2->2->4->3->5->null
.
public ListNode partition(ListNode head, int x) { ListNode leftDummy = new ListNode(0); ListNode left = leftDummy; ListNode rightDummy = new ListNode(0); ListNode right = rightDummy; while(head!=null){ if(head.val<x){ left.next = head; left = left.next; }else{ right.next = head; right = right.next; } head = head.next; } right.next = null; //important left.next = rightDummy.next; return leftDummy.next; }