题解 | #删除有序链表中重复的元素-I#

迭代法

• 怎么一步步穿针引线呢？
• 在遍历结点时，指针head 在推进，要维护一个虚拟头结点，它指向最初的head，确保能通过它找到头结点
• 当遇到 head.Val == head.Next.Val 时，开启循环删除 head.Next，通过 head.Next = head.Next.Next，直到不再值重复，那么此时和 head 重复的结点已经删完，就要继续推进 head，处理考察后面的结点
• 于是 head = head.Next，最后循环结束，整个链处理完毕，返回虚拟头结点的Next。

代码 golang

func deleteDuplicates( head *ListNode ) *ListNode {
    // 创建虚拟头结点
    dummy := new(ListNode)
    dummy.Next = head
    // 开启循环
    for head != nil && head.Next != nil {
        // 如果当前结点和下一结点的值相同
        if head.Val == head.Next.Val {
            // 则开启循环删除head.Next
            for head.Next != nil && head.Val == head.Next.Val {
                head.Next = head.Next.Next
            }
        } 
        // 现在处理完与head相同的结点，继续推进
        head = head.Next
    }
    return dummy.Next
}

递归法

deleteDuplicates 函数其实在 “治理” 头结点为 head 的链表，返回出新的链表

我们遍历结点，跳过重复的结点，来到不重复的结点，那么我们要“治理”从该点开始的链表

即 head.Next = deleteDuplicates(不重复的结点)

最后返回 head 即可

代码 golang

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
        }
    }
    head.Next = deleteDuplicates(head.Next)
    return head
}