划分链表

题目理解起来有点费劲：使所有小于x的节点都位于大于或等于x的节点之前，意思是只需要小于等于x的节点位于链表前面即可，不要求小于在前，等于在中，大于在后。

采用双哑节点+双指针，先构建中间链表，然后将两个链表合并：

• 哑节点指向两个中间链表的头部
• 指针指向两个中间链表的尾部

代码如下：

//
// Created by jt on 2020/9/24.
//
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param x int整型
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        ListNode dummy1(0), dummy2(0);
        ListNode *p = &dummy1, *q = &dummy2;
        ListNode *r = head;
        while (r) {
            if (r->val < x) {
                p->next = r; p = r;
            } else {
                q->next = r; q = r;
            }
            r = r->next;
        }
        p->next = dummy2.next;
        q->next = nullptr;
        return dummy1.next;
    }
};