連結清單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 上重要算法，以及一些經典算法
• 此處答案僅為參考，不一定是最優解，歡迎感興趣的讀者在評論區提供更優解