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;}
};