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.

这道题我本想用交换节点的方法处理，因为势必要保存当前节点的前一个节点，所以交换起来非常复杂

后来上网一查，发现可以直接使用创建两个链表然后合并的方法，不禁恍然大悟，忽略了链表的灵活性

既然partition方法可以很容易的实现，那么链表的快速排序也可以实现了，有时间再实现

ListNode* partition(ListNode* head, int x) {    if (head == nullptr)        return head;    ListNode temp1(0);    ListNode temp2(0);    ListNode *cur1 = &temp1;    ListNode *cur2 = &temp2;    temp1.next = head;    int tag = 0;    while (head != nullptr)    {        if (head->val < x)        {                        if (tag == 1)             {                cur1->next = head;                tag = 0;            }            cur1 = cur1->next;        }        else if (head->val >= x)        {                    if (tag == 0)            {                cur2->next = head;                tag = 1;            }            cur2 = cur2->next;                }        head = head->next;    }    cur1->next = cur2->next = nullptr;    cur1->next = temp2.next;    return temp1.next;}