1、思路

• 借助已有的节点创建一个新链表，用head与tail来标识链表的头部和尾部；

• 遍历原链表，若当前节点值小于x，就把该节点插入到新链表的头部，否则插入到尾部，操作完毕后需要更新头尾指针的位置，让他门指向新的头部或尾部。

2、代码

class Solution {
public:
    ListNode* partition(ListNode* node, int x) {
        if (node == nullptr || node->next == nullptr) return node;

        auto head = node, tail = node;      //两个指针分别代表头部和尾部
        while (node != nullptr)
        {
            auto next = node->next;         //先记录node的下一个节点

            if (node->val < x)
            {
                node->next = head;          //将node节点放到head节点之前
                head = node;                //再把head移动到新的头结点处
            }
            else
            {
                tail = tail->next = node;   //直接接到尾部，同时尾指针移到新的尾部
            }

            node = next;
        }

        tail->next = nullptr;               //断尾

        return head;
    }
};