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

在这篇Golang文章中，我们将使用递归和迭代的方法从已排序链表中删除重复值节点。

链表是一种数据结构，由一组节点组成，其中每个节点包含一个值和一个指向链表中下一个节点的指针。

语法

func deleteDuplicates(head *Node) *Node{…}

deleteDuplicates()函数用于从已排序链表中删除重复值节点。它使用头节点的指针作为参数。

算法

• 步骤1 - 首先，我们需要导入fmt包。

• 步骤2 - 现在，创建一个名为Node的链表单个节点的结构体。它包含两个成员，一个用于保存节点的数据值，第二个是指向链表中下一个节点的指针。

• 步骤3 - 定义函数insert()，以从头节点开始插入节点。

• 步骤4 - 创建一个名为deleteDuplicates的函数，它以链表的头作为输入并返回更新后的链表的头。它使用迭代方法遍历列表并删除重复节点。

• 步骤5 - 将当前指针初始化为指向列表的头。并使用循环遍历列表，直到当前成为nil。

• 步骤6 - 如果当前节点的数据值等于其下一个节点，则通过将next指针分配给下一个节点来删除下一个节点。

• 步骤7 - 如果当前节点的数据值不等于其下一个节点，则通过更新当前指针的next字段来移动到下一个节点。

• 步骤8 - 返回更新后的链表的头。

• 步骤9 - 启动main()函数。在main()函数中，调用insert()函数并向链表中添加节点。

• 步骤10 - 现在，调用deleteDuplicates()函数以删除重复项并打印更新后的列表。

• 步骤11 - 此外，使用fmt.Println()函数在屏幕上打印没有重复项的更新链表。

示例1

在这个示例中，我们将使用迭代方法定义一个deleteDuplicates()函数，用于从已排序链表中删除重复值节点。

package main

import "fmt"

type Node struct {
   value int
   next  *Node
}

// 插入排序链表
func insert(head **Node, value int) {
   newNode := &Node{value: value}
   if *head == nil || (*head).value >= value {
      newNode.next = *head
      *head = newNode
   } else {
      current := *head
      for current.next != nil && current.next.value < value {
         current = current.next
      }
      newNode.next = current.next
      current.next = newNode
   }
}

// 删除排序链表中重复的值节点
func deleteDuplicates(head *Node) *Node {
   if head == nil {
      return head
   }
   current := head
   for current.next != nil {
      if current.value == current.next.value {
         current.next = current.next.next
      } else {
         current = current.next
      }
   }
   return head
}

// 输出排序链表
func printList(head *Node) {
   for head != nil {
      fmt.Printf("%d ->", head.value)
      head = head.next
   }
   fmt.Println("nil")
}

func main() {
   var head *Node
   insert(&head, 4)
   insert(&head, 3)
   insert(&head, 1)
   insert(&head, 2)
   insert(&head, 3)
   insert(&head, 4)

   fmt.Println("排序链表：")
   printList(head)

   deleteDuplicates(head)

   fmt.Println("删除重复值后的链表：")
   printList(head)
}

输出

排序链表：
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> nil
删除重复值后的链表：
1 -> 2 -> 3 -> 4 -> nil 

实例 2

在这个例子中，我们使用递归方法定义了一个deleteDuplicates()函数，该函数用于从排序链表中删除重复的值节点。

package main

import (
   "fmt"
)

type Node struct {
   data int
   next *Node
}

// 递归删除排序链表中重复的值节点
func deleteDuplicates(head *Node) *Node {
   if head == nil || head.next == nil {
      return head
   }
   head.next = deleteDuplicates(head.next)
   if head.data == head.next.data {
      return head.next
   }
   return head
}

// 插入排序链表
func insert(head **Node, data int) {
   newNode := &Node{data: data, next: *head}
   *head = newNode
}

// 输出排序链表
func printList(head *Node) {
   for head != nil {
      fmt.Printf("%d ->", head.data)
      head = head.next
   }
   fmt.Println("nil")
}

func main() {
   var head *Node = nil

   insert(&head, 6)
   insert(&head, 6)
   insert(&head, 4)
   insert(&head, 3)
   insert(&head, 2)
   insert(&head, 2)
   insert(&head, 1)

   fmt.Println("排序链表：")
   printList(head)

   head = deleteDuplicates(head)

   fmt.Println("删除重复值后的链表：")
   printList(head)
}

输出

排序链表：
1 -> 2 -> 2 -> 3 -> 4 -> 6 -> 6 -> nil
删除重复值后的链表：
1 -> 2 -> 3 -> 4 -> 6 -> nil 

结论

我们成功编译和执行了一个go语言程序，使用迭代和递归方法删除排序链表中的重复值节点，并提供了两个示例。在第一个示例中，我们使用了迭代方法，在第二个示例中，我们使用了递归方法。