算法
(线性扫描) $O(n)$
为了方便处理边界情况,我们定义一个虚拟元素 $dummy$ 指向链表头节点。
然后从前往后扫描整个链表,每次扫描元素相同的一段,如果这段中的元素个数多于1个,则将整段元素直接删除。
时间复杂度
整个链表只扫描一遍,所以时间复杂度是 $O(n)$。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while (p->next) {
auto q = p->next;
while (q && p->next->val == q->val) q = q->next;
if (p->next->next == q) p = p->next;
else p->next = q;
}
return dummy->next;
}
};
家人们,最后这个p->next->next == q看好久了没看懂呜呜呜
代表没有重复的数
同感
q只移动一位的话 p->next->next == q 就成立。原因是一开始q = p->next,q只移动一位的话就变成了
q = p->next->next。
q只移动一位的话 p->next->next == q 就成立。原因是一开始q = p->next,q只移动一位的话就变成了
q = p->next->next。
现在明白了,感谢回复hh
懂了懂了,谢谢讲解qwq
滚蛋 这怎么代表没有重复的数呢
为啥不是啊求解释呜呜呜,看了好久
写成if (q->next == q) p = p->next; 这样好理解很多
q至少前进两位,当q只前进两位的时候,说明q经历的这两个点值不相同,所以p就往后移一位,当q移动两位以上时,说明这q经历的这些节点的值都相同,要将他们删除,同时p->next->next == q这个条件就不成立了,对应else语句中的p->next = q,p节点的next直接指向q节点,将中间的点删除
因为一开始q = p->next ,while语句里p->next->val == q->val一定成立一次,q就一定会向后移动一位。这时候若没有重复元素,q就在p->next->next这个节点上了。
为啥q一定会移动啊
while (q && p->next->val == q->val)里面 一开始我们初始化 q = p->next 所以q->val = p->next->val 所以while循环至少会运行一次
没有重复的数字的时候,q指针只走一步,对应p->next->next == q,确实是对应没有重复数字的情况😹
auto q = p->next;
while (q && p->next->val == q->val) q = q->next;
这里q = p -> next 那q ->val 不是永远等于 p -> next -> val 吗
q
是从p->next
开始,把所有和p->next
的值相等的一段都循环找出来。不考虑内存泄漏吗
需要delete dummy是吗?
一次内存泄露危害可以忽略
为什么这句话(q && p->next->val == q->val)写成( p->next->val == q->val&&q)就报seg错误??
q
如果是空节点,那么调用q->val
就会段错误。这里还会有顺序问题啊,我以为同时判断呢
对滴,条件表达式从左到右依次执行。
能不能来个大佬说说为什么要建立一个dummy指向头节点呀,还有这里的头结点有没有储存数据呀,我有点懵逼了,上面的操作似乎也没有删除头结点呀,跪求有个小回复
auto dummy = new ListNode (-1)这一句是建立一个值为-1,next指向空的节点,然后让这个节点作为虚拟节点插在原来头节点前面,目的是为了应对可能删除头节点的情况,而单链表只能找下一个节点,所以虚拟头节点就是为了能方便找到并删除头节点。另外,最后返回的是虚拟头节点的next节点作为头节点的链表,所以并不用真的删掉虚拟头节点
那大佬我想问一下,最后return 的是dummy的next,为什么不直接输出head呢,就算第一个被删了head也会返回一个空啊,比如4,4,4我用dummy的next没问题,但是用head返回就不行
牛逼
class Solution {
public:
ListNode deleteDuplication(ListNode head) {
if(head==NULL)
return NULL;
};
if (p->next && p->next->next == q) p = p->next;
这一步判断p->next好像没有什么用处?
对滴,这里
p->next
一定是存在的,所以可以去掉hh为什么我去掉后,提示Segmentation Fault啊
上面的代码已经是去掉之后的样子,是可以Accept的,你可以参考一下。
这个题老大似乎没有考虑四释放内存的呢?
是的,这里偷了个懒hh 面试的时候最好把内存释放掉
链表加头的方法学到了,没想到还可以这样规避掉表头前指针的特殊处理。每次写这种题的时候总要考虑表中元素个数为0、1、2的特殊情况,加上个头可以少些很多啰嗦的代码。
为什么把 return dummy->next; 换成 return head; 就报错了?
最后返回的时候为什么p->next不行,为什么一定要dummy->next呢?
用两个指针写的
加了点注释
class Solution {
public:
ListNode deleteDuplication(ListNode head) {
auto dummy = new ListNode(-1);
dummy->next = head;
};
考古qaq
请问这个return 是怎么写出来的,有什么讲究吗
一开始定义的dummy并非返回的头结点 dummy->next 才是
okok
太叼了
妙呀