86 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.

Important Points:

1. The trick and beauty of this question lies on "Preserve the original relative order of the nodes in each of the two partitions."
2. Use the dummy node to handle the empty list case, two dummy nodes needed.

Logic:

1. Create 2 linked lists to store two sections: one for the less than x part and the other for the bigger than x part
2. At the end, link the smaller linked list to the bigger linked list
3. Don't forget set the next node of the bigger linked list to null

Code:

    public ListNode partition(ListNode head, int x) {
       if(head==null||head.next==null)
              return head;

          ListNode small = new ListNode(-1);
          ListNode newsmallhead = small; //dummy node preserve the head of new linked list
          ListNode big = new ListNode(-1);
          ListNode newbighead = big;

          while(head!=null){
             if(head.val<x){
                 small.next = head;
                 small = small.next;
             }else{
                 big.next = head;
                 big = big.next;
             }
             head = head.next;
         }

         big.next = null;
         small.next = newbighead.next;

         return newsmallhead.next;
    }