题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

数据范围：链表长度满足 0 le n le 1000 0≤n≤1000 ，链表中的值满足 1 le val le 1000 1≤val≤1000

进阶：空间复杂度 O(n)*O(n) ，时间复杂度 O(n) *O(n)

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}

示例

// 输入：
{1,2,3,3,4,4,5}
// 返回值：
{1,2,5}

// 输入：
{1,1,1,8}
// 返回值：
{8}

代码实现

/**
 * [JZ76-简单]删除链表中重复的结点
 *
 * @param pHead Node类
 * @return Node类
 */
func deleteDuplication(pHead *Node) *Node {
    // 定义一个空链表
    var res = new(Node)
    // 给新链表添加表头
    res.Next = pHead
    cur := res
    // 从 next 节点开始遍历（前面加了一个表头）
    for nil != cur.Next && nil != cur.Next.Next {
        if cur.Next.Value == cur.Next.Next.Value {
            // 遇到前后节点相同情况，进行遍历，跳过所有相同节点
            tmp := cur.Next.Value
            for nil != cur.Next && cur.Next.Value == tmp {
                cur.Next = cur.Next.Next
            }
        } else {
            // 循环链表
            cur = cur.Next
        }
    }
    return res.Next
}