删除拼排序链表中的重复元素(最优解)
题目来源
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
,即删除重复节点后的链表头。