Golang程序：删除已排序链表中的重复值节点

在Go语言中，删除已排序链表中的重复值节点是一个经常用到的问题。本文将介绍如何使用Go语言编写程序来删除已排序链表中的重复值节点。

分析问题

在解决问题之前，我们需要了解一下已排序链表。已排序链表是一种数据结构，它将一系列节点按照特定的顺序链接起来。在已排序链表中，节点的值是按照升序或降序排列的。因此，在删除已排序链表中的重复值节点时，我们需要先了解它的属性。

已排序链表的每个节点都由两个部分组成：一个值和一个指向下一个节点的指针。在这个程序中，我们将创建一个结构体来表示每个节点。

// 节点
type Node struct {
    Val int
    Next *Node
}

在程序中，我们将使用两个指针来删除已排序链表中的重复值节点。第一个指针将指向链表的当前节点，第二个指针将指向节点的前一个节点。

实现程序

为了演示如何删除已排序链表中的重复值节点，我们将使用一个简单的例子。在这个例子中，我们将创建一个已排序链表，它包含一些重复的节点。

// 创建已排序链表
head := &Node{1, nil}
head.Next = &Node{1, nil}
head.Next.Next = &Node{2, nil}
head.Next.Next.Next = &Node{2, nil}
head.Next.Next.Next.Next = &Node{3, nil}

在这个例子中，已排序链表包含5个节点。其中，第1个节点和第2个节点的值相同，第3个节点和第4个节点的值相同。

我们将使用一个函数来删除已排序链表中的重复值节点。这个函数将接受已排序链表的头节点作为参数，并返回删除重复值节点后的已排序链表的头节点。

// 删除已排序链表中的重复值节点
func deleteDuplicates(head *Node) *Node {
    // 如果链表为空，则返回nil
    if head == nil {
        return nil
    }

    // 创建指向链表头节点的指针
    current := head

    // 创建指向链表头节点的前一个节点的指针
    prev := &Node{}

    // 创建map来查询节点是否重复
    m := make(map[int]bool)

    // 循环遍历链表
    for current != nil {
        if m[current.Val] { // 当前值已经出现过，删除该节点
            prev.Next = current.Next
        } else { // 当前值未出现过，将当前值存入map
            m[current.Val] = true
            prev = current
        }
        current = current.Next
    }

    // 返回删除重复值节点后的链表头节点
    return head
}

在这个函数中，我们使用一个map来存储每个节点的值。如果节点的值已经出现过，我们将删除该节点。否则，我们将在map中存储该节点的值，并将当前指针移动到该节点。

测试程序

为了测试我们的程序是否正确，我们将使用一个简单的测试函数。这个函数创建了一个已排序链表，并调用我们的deleteDuplicates函数来删除重复值节点。最后，它将输出删除重复值节点后的已排序链表。

// 测试已排序链表中删除重复值节点
func testDeleteDuplicates() {
    // 创建已排序链表
    head := &Node{1, nil}
    head.Next = &Node{1, nil}
    head.Next.Next = &Node{2, nil}
    head.Next.Next.Next = &Node{2, nil}
    head.Next.Next.Next.Next = &Node{3, nil}

    // 删除已排序链表中的重复值节点
    head = deleteDuplicates(head)

    //// 输出删除重复值节点后的已排序链表
    fmt.Println("Sorted linked list after removing duplicates:")
    current := head
    for current != nil {
        fmt.Print(current.Val, " ")
        current = current.Next
    }
}

在这个测试函数中，我们创建一个已排序链表，添加了一些重复的节点。然后，我们调用deleteDuplicates函数来删除重复值节点。最后，我们遍历已排序链表并输出节点的值。

完整程序

下面是我们的完整程序：

package main

import (
    "fmt"
)

// 节点
type Node struct {
    Val int
    Next *Node
}

// 删除已排序链表中的重复值节点
func deleteDuplicates(head *Node) *Node {
    // 如果链表为空，则返回nil
    if head == nil {
        return nil
    }

    // 创建指向链表头节点的指针
    current := head

    // 创建指向链表头节点的前一个节点的指针
    prev := &Node{}

    // 创建map来查询节点是否重复
    m := make(map[int]bool)

    // 循环遍历链表
    for current != nil {
        if m[current.Val] { // 当前值已经出现过，删除该节点
            prev.Next = current.Next
        } else { // 当前值未出现过，将当前值存入map
            m[current.Val] = true
            prev = current
        }
        current = current.Next
    }

    // 返回删除重复值节点后的链表头节点
    return head
}

// 测试已排序链表中删除重复值节点
func testDeleteDuplicates() {
    // 创建已排序链表
    head := &Node{1, nil}
    head.Next = &Node{1, nil}
    head.Next.Next = &Node{2, nil}
    head.Next.Next.Next = &Node{2, nil}
    head.Next.Next.Next.Next = &Node{3, nil}

    // 删除已排序链表中的重复值节点
    head = deleteDuplicates(head)

    // 输出删除重复值节点后的已排序链表
    fmt.Println("Sorted linked list after removing duplicates:")
    current := head
    for current != nil {
        fmt.Print(current.Val, " ")
        current = current.Next
    }
}

func main() {
    testDeleteDuplicates()
}