让我们一起啃算法----删除排序链表中的重复元素 II

三斤和他的喵的个人博客 / 47 / 1 / 创建于 3年前 / 更新于 3年前

删除排序链表中的重复元素 II（Remove-Duplicates-From-Sorted-List-II）

题干如下：

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例 1:
  输入: 1->2->3->3->4->4->5
  输出: 1->2->5
示例 2:
  输入: 1->1->1->2->3
  输出: 2->3

这题是上一篇让我们一起啃算法—-删除排序链表中的重复元素的进阶版。在上一篇中，我们删掉了重复的其他元素，仅保留一个元素，例如： 1 -> 2 -> 2 -> 3 变成 1 -> 2 -> 3。这题，则需要将仅保留的一个元素也删掉，例如： 1 -> 2 -> 2 -> 3 变成 1 -> 3。

解题思路

借上一篇的思路，我们需要在 current 指针基础上再多准备一个前置指针 pre 和一个有效值指针 really。really 指针始终指向有效链表的尾部，pre 指针指向 current 的前置节点，因为我们需要比较当前节点 current 的值是否和前置节点、后置节点的值相等，在单向链表中，后置节点很容易获取，即 current.next，但是前置节点不能很容易获取到，需要用 pre 记录。

初始化：由于需要一个前置节点，当 current 为链表的头节点 head 时前置节点其实是不存在的，为了方便后续的逻辑，我们需要设置一个初始节点 origin，使 pre、really 指向 origin，current 指向 head。

判断 current 的 val 与 current.next 的 val 和 pre 的 val 是否相等，相等的话，则 pre 指向 current， current 指向 current.next，如果不相等，则 really.next 指向 current，really 指向 current，同时 pre 指向 current，current 指向 current.next，大致思路如上。但是这里有个注意事项：

按照上面的逻辑，pre 指向 current 后，需要将 pre.next 置为空，例如链表为： 1 —-> 2 —-> 2，如果不把节点1 与节点2 的连接断开，后续返回的 origin.Next 链表结构为： 1 —-> 2 —-> 2 仔细体会一下！

流程图如下：

代码实现

GO语言实现

func deleteDuplicates(head *ListNode) *ListNode {
    origin := &ListNode{Val:0}
    current := head
    pre := origin
    really := origin
    for current != nil {
        // 因为新引入了一个初始节点，防止和原始链表的第一个节点冲突，比如第一个节点刚好 Val 也为 0
        // 那么单纯 current.Val != pre.Val 判断是不够的，需要加入 pre == origin 这个判断
        if (pre == origin || current.Val != pre.Val) && (current.Next == nil || current.Val != current.Next.Val) {
            really.Next = current
            really = current

        }

        pre = current
        current = current.Next

        // 这里需要将 pre 和 current 之间的连接断开，例如链表为： 1---->2---->2，
        // 如果不把 节点1 与 节点2 的连接断开，后续返回的 origin.Next 链表结构为： 1---->2---->2 仔细体会一下！
        pre.Next = nil
    }
    return origin.Next
}