刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

思路

这道题最难的地方感觉在于状态梳理
可以分别来看下

1、【状态1】now 和 now.Next 不相等

这时now 和 tail 均步进即可（tail 拼接 now 也是一样的效果）

2、【状态2】now 和 now.Next 相等

此时不能直接拼接了，而是需要持续步进now，直到找到不相等的节点

3、【状态3】跳过重复节点时，now 和 now.Next 不相等

此时虽然发现了不相等的节点，但是now所处节点是有重复的节点，还是只能步进，不能拼接。
不过此时会是一个跳出当前跳过重复节点操作的结束状态

4、【状态2】跳过重复节点后，now 和 now.Next 相等

此时其实等同于状态2，又发现了新的重复节点

5、【状态1】跳过重复节点后，now 和 now.Next 不相等

此时其实等同于状态1，都是跳过重复节点操作之外发现了一个不相等节点

6、【状态4】跳过重复节点后，now.Next 为 nil

如果不相等节点后发现链接到了终点那么其实不用做任何操作，前面都已经拼接完毕，直接返回就好

7、【状态5】跳过重复节点时，now.Next 为 nil

但是走到终点会有个特殊状态，那就是在跳过重复节点时发现到了终点，而此时的状态，tail还在指向后续的重复节点，所以需要把tail的后续直接链接到nil

或者可以把这一步当做特殊操作，在状态流转之外处理，代码中表现就是记录一个状态，循环之外再处理

至此，上代码

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 辅助记录头结点
    veryHead := &ListNode{Next: head}
    // 辅助记录当前新链表尾部节点
    tail := veryHead
    // 辅助搜索非重复节点
    now := head
    for now != nil {
        if now.Next != nil && now.Next.Val == now.Val {
            x := now.Val
            // 清理重复项，
            for now.Next != nil && now.Next.Val == x {
                now = now.Next
            }
            // 此时now位置是最后一个重复项，所以再进一步到下个非重复点再行判断
            now = now.Next
            // 清理重复直接到了末尾则额外处理下拼接
            // 或者记录个状态在退出循环后再处理也可
            if now == nil {
                tail.Next = now
            }
        } else {
            // 非重复节点，拼上
            tail.Next = now
            tail = now
            now = now.Next
        }
    }
    return veryHead.Next
}