LeetCode - 面试题 02.04. 分割链表

题目

面试题 02.04. 分割链表 - 力扣（LeetCode）

双指针合并思路

这个双指针的思路是将原链表分成两个子链表，然后再合并它们：

创建两个子链表：

• 一个子链表用于存放所有小于x的节点（smalldummy开头）

• 一个子链表用于存放所有大于等于x的节点（largedummy开头）

使用双指针维护两个子链表：

• smallptr始终指向小值链表的尾部

• largeptr始终指向大值链表的尾部

• 这两个指针使我们能够在O(1)时间内向各自的链表添加新节点

遍历原链表：

• 对于每个节点，根据其值与x的比较结果，将其添加到对应的子链表中

• 重要的是，我们不是创建新节点，而是直接移动原链表中的节点

合并两个子链表：

• 将大值链表的末尾节点的next指针设为nullptr（防止循环引用）

• 将小值链表的末尾连接到大值链表的开头

这种方法的优势在于：

• 时间复杂度为O(n)，只需遍历链表一次

• 空间复杂度为O(1)，只使用了常数额外空间（两个dummy节点）

读者可能的错误写法

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr)
        {
            return nullptr;
        }
        ListNode* smalldummy = new ListNode(0);
        ListNode* largedummy = new ListNode(0);

        ListNode* smallptr = smalldummy;
        ListNode* largeptr = largedummy;

        while(head)
        {
            if(head->val < x)
            {
                smallptr->next = head;
                smallptr = smallptr->next;
            }
            else
            {
                largeptr->next = head;
                largeptr = largeptr->next;
            }
            head = head->next;
        }
        smallptr->next = largedummy->next;

        return smalldummy->next;
    }
};

没有将大值链表的末尾节点的next指针设置为nullptr。

当你遍历完原链表后，大值链表的最后一个节点(largeptr)的next指针仍然指向原链表中的下一个节点，这可能会导致循环引用。

正确写法

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr)
        {
            return nullptr;
        }
        ListNode* smalldummy = new ListNode(0);
        ListNode* largedummy = new ListNode(0);

        ListNode* smallptr = smalldummy;
        ListNode* largeptr = largedummy;

        while(head)
        {
            if(head->val < x)
            {
                smallptr->next = head;
                smallptr = smallptr->next;
            }
            else
            {
                largeptr->next = head;
                largeptr = largeptr->next;
            }
            head = head->next;
        }
        largeptr->next = nullptr;  // 这行很重要，防止循环引用
        smallptr->next = largedummy->next;

        return smalldummy->next;
    }
};