牛客网高频算法题系列-BM16-删除有序链表中重复的元素-II

题目描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

原题目见：BM16 删除有序链表中重复的元素-II

解法一：链表遍历

首先，考虑特殊情况，如果链表为空或者只有一个结点，不会有重复的元素，返回原链表。

否则，遍历链表判断是否有重复元素，处理过程如下：

• 首先，因为头结点也可能重复，所以使用一个虚拟头结点dummyNode；

• 然后，用lastNonRedundantNode为上一个不重复的结点，初始化为头结点，count记录该结点的元素的重复次数，初始为1；

• 然后从原链表的第二个结点开始遍历；

• 如果当前结点的值和lastNonRedundantNode不相同，判断lastNonRedundantNode出现的次数，如果只出现过一次，则是一个不重复的结点，更新pre；否则不更新pre。更新lastNonRedundantNode，并将count重置为1。

• 如果当前结点的值和lastNonRedundantNode相同，则将count加1。

• 最后，判断最后一个结点出现的次数，如果count为1，则也是不重复的结点。

最后，返回新构造的不重复元素的链表。

代码

$1.01^\approx 37.7834343329$  
$0.99^\approx 0.02551796445$  
相信坚持的力量！