链表08--删除链表中重复节点

链表08--删除链表中重复节点-jz56

• ​​题目概述​​
• ​​解析&参考答案​​
• ​​注意事项​​
• ​​说明​​

题目概述

• 算法说明

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

• 测试用例

  输入：

  {1,2,3,3,4,4,5}

  输出：

  {1,2,5}

解析&参考答案

• 解析

  map 获取重复节点，然后递归获取新的链表；先使用map记录下所有重复节点，然后递归构建不重复的链表。

• 参考答案

vim jz56.go
package main

import "fmt"

type ListNode struct {
    Val  int
    Next *ListNode
}

func CreateList(array []int) *ListNode {
    if len(array) == 0 {
        return nil
    }
    head := &ListNode{array[0], nil}
    p := head
    for i, val := range array {
        if i == 0 {
        } else {
            item := &ListNode{val, nil}
            p.Next = item
            p = p.Next
        }
    }
    return head
}

func PrintList(head *ListNode) {
    if head == nil {
        fmt.Print("nil")
    } else {
        p := head
        for p != nil {
            if p.Next != nil {
                fmt.Printf("%d->", p.Val)
            } else {
                fmt.Printf("%d\n", p.Val)
            }
            p = p.Next
        }
    }
}

func getNewList(head *ListNode, m map[int]int) *ListNode {
    if head == nil {
        return head
    }
    p := head
    if m[p.Val] > 1 {
        p = getNewList(p.Next, m)
    } else {
        p.Next = getNewList(p.Next, m)
    }
    return p
}

func deleteDuplication(pHead *ListNode) *ListNode {
    if pHead == nil || pHead.Next == nil {
        return pHead
    }
    m := make(map[int]int)
    p := pHead
    for p != nil {
        m[p.Val]++
        p = p.Next
    }
    headNew := getNewList(pHead, m)
    return headNew
}

func main() {
    array := []int{1, 2, 3, 3, 4, 4, 5}
    //array := []int{1, 1, 2, 3, 3, 4, 4, 5}
    //array := []int{1, 2, 1, 3, 3, 4, 4, 5}
    //array = []int{1, 1}
    //array = []int{}
    head := CreateList(array)

    head = deleteDuplication(head)
    PrintList(head)
}      

注意事项

1. 剑指offer 和网络上大部分解析没有处理不连续重复节点的情况，例如 {1, 2, 1, 3, 3, 4, 4, 5}，会被处理为{1，2，1，5}，实际上处理为{2，5}才更加符合删除重复节点的题意。

说明

1. 当前使用 go1.15.8
2. 参考​​牛客网--剑指offer​​ 标题中jzn(n为具体数字)代表牛客网剑指offer系列第n号题目，例如 jz01 代表牛客网剑指offer中01号题目。

• 笔者最近在学习 golang，因此趁机通过数据结构和算法来进一步熟悉下go语言
• 当前算法主要来源于剑指 offer，后续会进一步补充 LeetCode 上重要算法，以及一些经典算法
• 此处答案仅为参考，不一定是最优解，欢迎感兴趣的读者在评论区提供更优解