思路

怎么一步步穿针引线？

  • 排好序的链表，重复节点会相邻出现，遍历节点时，如果 head.val == head.next.val，就删掉 head.next。即让 head 指向 head.next.next
    image.png

  • 然后，作为重复结点中的第一个，head 结点也要被删掉。
    image.png

  • 所以要维护一个 head 的上一结点 prev，用来删 head，即让 prev 取代 head 指向 head.next
    image.png

  • 接着让 head 推进，考察下一个 head 和 head.next
    image.png

  • 经过这波循环，我们删掉了与 head 结点值重复的结点。然后在下一轮循环中继续上面操作

上面是遇到重复结点的情况，prev 会去 “跟上” head。

如果没有遇到重复结点呢？head 要步进，考察下一个 head，注意 prev 也要步进，“跟上” head

迭代版 golang

func deleteDuplicates(head *ListNode) *ListNode {
    // 创建虚拟头结点
    dummy := new(ListNode) 
    // 让虚拟头结点指向head
    dummy.Next = head
    // 让prev初始指向虚拟头结点
    prev := dummy
    // 开启遍历
    for head != nil && head.Next != nil {
        // 如果出现重复结点
        if head.Val == head.Next.Val {
            // 开启循环删结点
            for head.Next != nil && head.Val == head.Next.Val {
                head.Next = head.Next.Next
            }
            // 此时head也要删，让prev指向head.Next
            prev.Next = head.Next
        } else {
            // 如果head和head.Next不是重复结点，则prev步进，head也步进
            prev = prev.Next
        }
        // 不管head和head.Next是不是重复结点，head都要步进
        head = head.Next
    }
    return dummy.Next
}

递归法

deleteDuplicates 函数的定义是“治理”头结点为 head 的链表，返回出新的链表

我们遍历结点，跳过重复的结点，来到不重复的结点，那么上面这个“大问题”的答案就等于 deleteDuplicates(不重复的结点)

它们是规模不一样的同一问题。

如果没有遇到重复的结点呢，那么当前的 head 是需要保留的，然后 head.Next = deleteDuplicates(head.Next)

func deleteDuplicates(head *ListNode) *ListNode {
    // 特判
    if head == nil || head.Next == nil {
        return head
    }
    // 开启循环
    if head.Val == head.Next.Val {
        for head.Next != nil && head.Val == head.Next.Val {
            head = head.Next
        }
        return deleteDuplicates(head.Next)
    } else {
        head.Next = deleteDuplicates(head.Next)
        return head
    }
}

感谢阅读，希望能解决你的困惑