算法题学习 --- 删除有序链表中重复的元素 -I
题目
描述
删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次例如：给出的链表为 1→1→2,返回 1→2.给出的链表为 1→1→2→3→3,返回 1→2→3.
数据范围：链表长度满足 0≤n≤100，链表中任意节点的值满足∣val∣≤100
进阶：空间复杂度 O(1)，时间复杂度 O(n)
示例 1
复制代码
示例 2
复制代码
分析
分析特殊情况
不难看出，在链表为空和链表只有一个元素时，只需要返回输入的链表头即可。
分析一般情况
由于需要删除相同的元素，那么我们就保留遇到的第一个元素即可，因为链表只能顺序访问，不能够逆序访问，如果发现后面的元素的值与它相等，那么就删除新元素，指向再下一个元素，继续判断；如果不等，说明可以继续往后遍历。
基于这样的想法，我们可以设定两个指针一个指向之前的元素 pPre，初始化为头结点，pCur 为当前遍历的元素，遍历链表直到 pCur 为空指针。
当 pPre 的元素值与 pCur 的元素值相等时，两者均往后移；
当 pPre 的元素值与 pCur 的元素值不等时，删除 pCur 指向的元素，并更新 pCur 为下一个元素，将 pPre 的指针执向 pCur。
代码示例
如分析所述，需要注意的是，这里对节点进行删除时，需要事先分配一个临时变量存储需要释放的指针。
复制代码
版权声明: 本文为 InfoQ 作者【桑榆】的原创文章。
原文链接:【http://xie.infoq.cn/article/d1a971ac281a71dc28c5bc139】。文章转载请联系作者。
北海虽赊，扶摇可接；东隅已逝，桑榆非晚！ 2020-02-29 加入
Android手机厂商-相机软件系统工程师 爬山/徒步/Coding
评论