[LeetCode] 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.

解题思路一：

弄两个dummyhead，原list从左向右扫描，小于x的加在第一个之后，大于等于加到第二个之后，最后合并两个list。

解题思路二：

两个指针，左指针开始指向dummyhead，右指针指向head，如果右指针所指处小于x，两指针同时往右移动，直到右指针指向第一个大于等于x的node，接下来每当右指针的下一个小于x，就把那个node插到左指针之后，右指针则向前跳一步。

    public ListNode partition(ListNode head, int x) {       
        ListNode dummyhead = new ListNode(0);
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        ListNode temp = new ListNode(0);
        ListNode firstright = new ListNode(0);
        dummyhead.next = head;
        left = dummyhead;
        right = head;        
        if(right == null)
            return null;        
        while(right.val<x)
        {
            right = right.next;
            left = left.next;
            if(right == null)
                return head;
        }        
        firstright = right;      //记录第一个大于等于x的node，后面交换位置时需要。
        while(right.next!=null)
        {
            if(right.next.val>=x)
                 right = right.next;               
            else
            {
                temp = right.next.next;
                left.next = right.next;
                right.next = temp;
                left = left.next;
                left.next = firstright;
            }
        }
        return dummyhead.next;      
    }
}