本次刷题日记的第 105 篇，力扣题为：82. 删除排序链表中的重复元素 II
一、题目描述：
继续来做咱们的刷题试炼，删除排序链表中的重复元素 II
二、这道题考察了什么思想？你的思路是什么？
题目字数不多，表达的意思相当明确，本题要求我们删除链表中数值重复的所有节点，而不仅仅是删除重复多的节点
分析
根据题目要求，第一咱们需要考虑如何去找到数值重复的节点
第二我们需要考虑我们删除节点的位置，这个待删除的节点若是链表头，链表中间，链表尾巴的时候，我们需要如何抠掉我们要删除的节点，且还能让其他未被删除的节点正常连接
找到重复的节点这个简单，题目说明了这个链表是排序过的，因此咱们直接遍历链表，判断当前节点的数值是否和下一个节点的数值相等即可，若相等，则继续往下偏移是否再下一个节点也是相等的，直到找到第一个不相等的节点为止
例如题目中给出的示例 ：head = [1, 1, 1, 2, 3]
如果第一个节点为头节点，那么咱们很明显最终头结点要偏移到数值为 2 的节点上面来
那这个时候其实我们就要为这种需要不断删除头结点的情况来做判断了，我们也可以使用简单高效的方式，那就是咱们可以定义一个假的头结点，例如这样
那么这个时候咱们就不用考虑头结点的事情了，因为 头结点是永远不会被删除的，咱们直接按照逻辑去找相同的节点，找到挨着的最后一个相同的节点后，便将 Fake 节点的 next 指针指向下一个不同值的节点即可，例如这样
这个时候，咱们直接返回 Fake 节点的 next 即可
那么，接下来，咱们就来开心的撸代码吧
三、编码
根据上述逻辑和分析，我们就可以翻译成如下代码
- 定义一个 Fake 节点指向链表头，做一个假的头结点
- 遍历链表，找到重复的节点后，将 Fake 指针指向下一个节点，然后继续遍历，使用同样的方式进行处理即可
编码如下：
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteDuplicates(head *ListNode) *ListNode { if head == nil { return nil } dummy := &ListNode{0, head} cur := dummy for cur.Next != nil && cur.Next.Next != nil { if cur.Next.Val == cur.Next.Next.Val { x := cur.Next.Val for cur.Next != nil && cur.Next.Val == x { cur.Next = cur.Next.Next } } else { cur = cur.Next } } return dummy.Next }
四、总结：
本次的这种实现方式比较讨巧，咱们引入了一个哑结点，咱们直接去遍历题目给出的链表就可以了，都不用考虑重复的元素是在链表头，链表中和链表尾巴，因此咱们的时间复杂度是 O(n)
空间复杂度是 O(1) ，咱们引入的都是常熟级别的空间消耗
原题地址：82. 删除排序链表中的重复元素 II
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
