算法题学习 --- 删除有序链表中重复的元素 -II
题目
描述
给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为 1→2→3→3→4→4→5, 返回 1→2→5.给出的链表为 1→1→1→2→3, 返回 2→3.
数据范围：链表长度 0≤n≤10000，链表中的值满足∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
示例 1
示例 2
分析
分析特殊情况
由题目我们可以知道，当链表为空或者链表只有一个元素时，只需要返回链表头即可。
分析一般情况
首先由于我们不知道是否需要删除头结点，最好新建一个 dummy 节点指向头结点；
然后我们对链表进行遍历，检查前后两个元素是否相等：
如果不等，则往后继续遍历；
如果相等，那么我们需要进行内循环，向后找到所有相等的节点，并删除它们。
这里我们采用了三个节点 pPrePre 初始化为 dummy 节点，pPre 初始化为 head，pCur 初始化为 head->next，然后遍历对比 pPre 与 pCur 的值，如果不等，则更新上面三个指针，如果相等，则先删除 pCur 到最后一个相同值的节点，然后删除 pPre，然后建立新的连接，并更新。
最后返回 pReturn->next.
代码示例
注意，这里也涉及到我们在删除节点时的操作，需要使用一个临时变量缓存需要删除的节点，还有，我们最开始创建的 dummy 节点也不要忘记一并删除。
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/57cf0b3ff2250773e52b07aa8】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论