Golang 删除排序链表中的重复节点

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

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

语法

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

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

步骤

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

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

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

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

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

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

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

• 步骤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("Sorted Linked List:")
   printList(head)

   deleteDuplicates(head)

   fmt.Println("List after deleting duplicate Value Nodes:")
   printList(head)
}

输出

Sorted Linked List:
1 -> 2 -> 3 -> 3 -> 4 -> 4 -> nil
List after deleting duplicate Value Nodes:
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("Sorted Linked List:")
   printList(head)

   head = deleteDuplicates(head)

   fmt.Println("Linked List after deleting duplicate Value Nodes:")
   printList(head)
}

输出

Sorted Linked List:
1 -> 2 -> 2 -> 3 -> 4 -> 6 -> 6 -> nil
Linked List after deleting duplicates:
1 -> 2 -> 3 -> 4 -> 6 -> nil

结论

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