[数据结构与算法]Golang - 82. 删除排序链表中的重复元素 II

题目描述

详情可以查看题目链接

解题思路

1. 整体思路
   1.1. 创建虚拟头节点和两个一前(pre)一后(cur)的指针
   1.2. cur 每走一步都判断 pre 的值是否和 next 的值相同
   1.3. 如果相同，就一直往后走，知道不相同
   1.4: 执行删除操作

2. 图解

然后循环执行上图流程，直至 cur 或者 cur.Next 为空，表示链表遍历完成

代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    // 新建虚拟节点
    ret := &ListNode{-1, head}
    // 创建两个指针，一前一后
    pre := ret
    cur := head


    for cur != nil && cur.Next != nil{
        if pre.Next.Val != cur.Next.Val  {
            cur = cur.Next
            pre = pre.Next
        } else {
            for cur != nil && cur.Next != nil && cur.Next.Val == pre.Next.Val {
                cur = cur.Next
            }
            pre.Next = cur.Next
            cur = cur.Next
        }
    }

    return ret.Next
}