C++，用两个链表，先分再合

直观来说我们只需维护两个链表small 和large 即可： small 链表按顺序存储所有小于 x 的节点，large 链表按顺序存储所有大于等于 x 的节点。遍历完原链表后，将small 链表尾节点指向large 链表的头节点，完成两个链表的合并。

为了实现上述思路，我们设smallHead 和 largeHead 分别为两个链表的哑节点，即它们的next 指针指向链表的头节点，这样做的目的是为了更方便地处理头节点为空的边界条件。同时设置small 和large 节点指向当前链表的末尾节点。 开始时，smallHead=small,largeHead=large来保存两个哑节点。 随后，从前往后遍历链表，判断当前链表的节点值是否小于 x，如果小于就将small 的 next 指针指向该节点，否则将 large 的 next 指针指向该节点。

遍历结束后，我们将 large 的 next 指针置空，这是因为当前节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x 的节点，我们需要切断这个引用。同时将 small 的next 指针指向、largeHead 的next 指针指向的节点，即真正意义上的 large 链表的头节点。最后返回 smallHead 的 next 指针即为我们要求的答案。

ListNode* partition(ListNode* head, int x) {
        // write code here
        ListNode* small = new ListNode(0);
        ListNode* smallHead = small;
        ListNode* large = new ListNode(0);
        ListNode* largeHead = large;
        while (head != nullptr) {
            if (head->val < x) {
                small->next = head;
                small = small->next;
            } else {
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = nullptr;
        small->next = largeHead->next;
        delete largeHead;
        largeHead=nullptr;
        ListNode* ret=smallHead->next;
        delete smallHead;
        smallHead=nullptr;
        return ret;
}

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/partition-list/solution/fen-ge-lian-biao-by-leetcode-solution-7ade/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。