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->null and x = 3,
return 1->2->2->4->3->5->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 || x == 0) return head;

        ListNode leftdummy = new ListNode(0);

        ListNode rightdummy = new ListNode(0);

        ListNode left = leftdummy, 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;

        left.next = rightdummy.next;

        return leftdummy.next;

    }

}