本题为1月15日力扣每日一题
题目来源:力扣第82题
题目tag:链表
双指针
题面
题目描述
给定一个已排序的链表的头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 \leq Node.val \leq 100 $
题目数据保证链表已经按升序排列
思路分析
本题要做的其实就两件事,一是在链表中找到重复元素,二是删除链表的一些元素.
第一件事很好完成,只需要在编译时看一看当前元素和后一个元素的值是否相等即可.注意预防空指针.
对于第二件事,我们知道,删除链表中的一个元素,需要两个指针,一个指向要删除的元素,另一个指向删除元素的前驱元素(如果删除一连串元素,显然指向这一串元素中第一个元素的前驱元素).然后通过如下代码即可删除当前元素:
prev->next = now->next;
// 部分语言注意手动释放内存空间
如果你想不通上面的代码,这里简单解释一下.因为链表是通过next
指针来确定前驱后继关系的,只要将当前元素从next
指针链中移除即可,本题是单向链表,那么只需要把指向这个元素的指针移走,那么在next
指针链中就找不到当前元素了,这样就完成了删除.
但是这样有一个问题,如果要删除的节点是整个链表的第一个节点呢?这样没有办法取得这个元素的前驱结点.这里有两个方法,一个是特判开头,把第一个不重复的元素作为头结点,无视前面的节点;另一个是构造一个虚拟的头结点,产生出第一个节点的前驱节点.此处出于个人习惯,采用第二种方式.实际上在其他涉及删除的问题中,构造虚拟头结点往往能大大简化分类讨论特判的过程.
由此,此题我们先构造一个虚拟的头结点,然后用两个指针来遍历这个链表.每次找到一串相同元素的最后一个元素,然后通过上面所说的方式将这一串连续的元素全部删除即可.文章来源:https://www.toymoban.com/news/detail-790895.html
参考代码
/**
* 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) {
// 创建虚拟头结点
ListNode h(0, head);
ListNode *prev = &h,*now = head;
// 遍历整个链表
while(now != nullptr && now->next != nullptr) {
bool flag = false;
// 找到该元素的最后一个
while(now != nullptr && now->next != nullptr && now->val == now->next->val) {
flag = true;
ListNode *p = now;
now = now->next;
delete p; // 释放内存空间
}
if(flag) {
// 出现重复,删掉所有重复的元素
prev->next = now->next;
ListNode *p = now;
now = now->next;
delete p; // 释放内存空间
} else {
// 没有重复,继续往后遍历
prev = prev->next;
now = now->next;
}
}
// 返回时去掉头结点
return h.next;
}
};
"正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯" ---亚里士多德文章来源地址https://www.toymoban.com/news/detail-790895.html
到了这里,关于「双指针」删除排序链表中的重复元素 II(力扣第82题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!