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.

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

return 1->2->2->4->3->5->null.

题意：是给定一个x的值，小于x都放在大于等于x的前面，并且不改变原链表node之间的相对位置。

new两个新链表，一个用来创建所有小于x的链表，一个用来创建所有大于等于x的链表，双dummy node

遍历整个链表时，如果当前node的val小于x，接在小链表上，反之，接在大链表上。

最后，小链表和大链表相接，别忘了把大链表的结尾指向null。

注意：这样就保证了原链表node间的相对顺序没有改变，而仅仅做了链表node与x的大小判断。所以，这道题是不需要任何排序操作的。

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */


class Solution {
public:
    /*
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
    ListNode * partition(ListNode * head, int x) {
        // write your code here
        if (head == NULL) {
            return NULL;
        }
        ListNode* lessTarget = new ListNode(0);
        ListNode* MoreTarget = new ListNode(0);
        ListNode* lessDummy = lessTarget;
        ListNode* moreDummy = MoreTarget;


        while (head != NULL) {
            if (head->val < x) {
                lessDummy->next = head;
                lessDummy = lessDummy->next;
            } else {
                moreDummy->next = head;
                moreDummy = moreDummy->next;
            }
            head = head->next;
        }
        moreDummy->next = NULL;
        lessDummy->next = MoreTarget->next;
        return lessTarget->next;
    }
};