题解 | 链表分割

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        if (!pHead) {
            return nullptr;
        }
        ListNode* dummy1 = new ListNode(0);
        ListNode* dummy2 = new ListNode(0);
        ListNode* curr1 = dummy1;
        ListNode* curr2 = dummy2;
        ListNode* origin = pHead;
        while (origin) {
            if (origin -> val < x) {
                curr1 -> next = origin;
                curr1 = curr1 -> next;
            } else {
                curr2 -> next = origin;
                curr2 = curr2 -> next;
            }
            origin = origin -> next;
        }
        // curr2可能还指向原来的pHead中的某个节点，可能有环
        curr2 -> next = nullptr;
        curr1 -> next = dummy2 -> next;
        return dummy1 -> next;
    }
};

思路：

• 使用两个虚拟头节点 dummy1 和 dummy2 分别存储小于 x 的节点和大于或等于 x 的节点。
• 遍历原链表，根据节点值与 x 的关系将节点分配到 dummy1 或 dummy2 的链表中。
• 最后将 dummy1 的链表尾部连接到 dummy2 的链表头部，形成最终的分区链表。

需要注意

复杂度

• 时间复杂度：O(n)， 遍历一次pHead，n为链表长度C++
• 空间复杂度：O(1)，仅使用了常数级别的额外空间（虚拟头节点）