当前位置：首页 > news >正文

删除拼排序链表中的重复元素（最优解）

news 来源：原创 2025/5/15 1:26:07

题目来源

82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

题目限制

最优解实现题目的解决

思路分析

在处理这个问题时，我们面对的是一个已排序的链表，要求删除所有重复数字的节点，只保留不同的数字。解题的关键在于利用链表已排序这一特性，通过一次遍历完成节点的删除操作。

1. 哨兵节点的引入

由于链表的头节点可能会被删除（例如输入链表 [1,1,2] 时，头节点 1 会被删除），所以引入一个哨兵节点（dummy node）。这个哨兵节点的值可以是任意值，但其作用是作为链表的新头，始终指向第一个不重复的节点。这样在处理链表头节点的删除操作时，就无需特殊处理，简化了代码逻辑。

2. 双指针遍历

我们使用两个指针，一个指针 prev 初始指向哨兵节点，另一个指针 curr 指向链表的头节点 head。
curr 指针用于遍历链表，prev 指针则用于记录当前不重复节点的前一个节点。在遍历过程中，curr 指针不断前进，同时检查 curr 及其后续节点的值是否与当前 curr 的值相同。

3. 重复节点的处理

当发现 curr 的值与下一个节点的值相同时，说明存在重复节点。此时，curr 指针需要不断向后移动，直到找到一个与当前值不同的节点，这样就跳过了所有重复的节点。
例如，链表为 [1,1,1,2,3]，当 curr 指向第一个 1 时，发现下一个节点也是 1，curr 就一直移动到值为 2 的节点，此时 curr 指向了 2。
然后，将 prev 的 next 指针直接指向 curr，这样就跳过了所有重复的节点。即 prev 原本指向哨兵节点，现在将其 next 指向 2，从而删除了所有值为 1 的节点。

4. 指针移动

在处理完重复节点后，prev 指针移动到 curr 所在位置，因为 curr 现在指向的是一个新的不重复节点。而 curr 指针继续向前移动，准备检查下一组节点。

5. 结束条件

当 curr 指针遍历完整个链表，即 curr 为 null 时，遍历结束。此时，哨兵节点 dummy 的 next 指针指向的链表就是删除所有重复节点后的结果链表，直接返回 dummy.next 即可。

通过这种方法，我们能够在一次遍历链表的过程中，有效地删除所有重复节点，时间复杂度为，其中是链表的长度。同时，由于只使用了有限的额外指针，空间复杂度为。这种方法简洁高效，充分利用了链表已排序的特性。

具体代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if(!head)return head;ListNode* cur=new ListNode(-1);cur->next=head;ListNode* pre=cur;while(cur->next&&cur->next->next){if(cur->next->val==cur->next->next->val){int c=cur->next->val;while(cur->next&&cur->next->val==c){cur->next=cur->next->next;}}else {cur=cur->next;}}return pre->next;}
};

这段 C++ 代码定义了Solution类中的deleteDuplicates函数，用于删除已排序链表中重复数字的节点。先判断链表是否为空，空则直接返回。接着创建一个值为 -1 的哨兵节点cur，其next指向原链表头head，pre指向cur。通过while循环，当cur的下一个及下下个节点存在时，若二者值相等，记录该值并跳过所有相同值的节点；否则cur后移。最后返回pre的next，即删除重复节点后的链表头。