golang链表删除重复项

使用Golang链表删除重复项

链表是一种常用的数据结构，使用起来非常方便。在某些情况下，我们需要从链表中删除重复的元素。本文将介绍如何使用Golang来实现删除链表中重复元素的功能。

首先，我们需要定义一个链表节点的结构体：

```go type ListNode struct { Val int Next *ListNode } ```

接下来，我们可以编写一个函数来删除链表中重复的元素：

```go func deleteDuplicates(head *ListNode) *ListNode { current := head for current != nil && current.Next != nil { if current.Val == current.Next.Val { current.Next = current.Next.Next } else { current = current.Next } } return head } ```

在这个函数中，我们使用了双指针的方法。我们将一个指针指向当前节点，另一个指针指向下一个节点。通过比较这两个节点的值，我们可以判断是否有重复元素。如果有重复元素，则将当前节点的Next指针指向下一个节点的Next指针，从而实现删除操作。如果没有重复元素，则将当前节点指针后移。最后，返回链表的头节点。

接下来，让我们来测试一下这个函数：

```go func main() { // 创建一个链表 head := &ListNode{Val: 1} node1 := &ListNode{Val: 1} node2 := &ListNode{Val: 2} head.Next = node1 node1.Next = node2 // 删除链表中的重复元素 result := deleteDuplicates(head) // 打印结果 current := result for current != nil { fmt.Println(current.Val) current = current.Next } } ```

运行以上代码，我们将会得到输出结果：1，2。可以看到重复的1已经被成功删除了。

上面的函数只适用于有序链表。如果我们要删除无序链表中的重复元素，我们需要修改一下代码：

```go func deleteDuplicates(head *ListNode) *ListNode { hashSet := make(map[int]bool) dummy := &ListNode{Next: head} prev := dummy current := head for current != nil { if hashSet[current.Val] { prev.Next = current.Next } else { hashSet[current.Val] = true prev = prev.Next } current = current.Next } return dummy.Next } ```

在这个函数中，我们使用了一个哈希集合来存储已经出现过的元素。遍历链表的过程中，对于每个节点，我们首先判断它是否在哈希集合中出现过。如果出现过，则直接删除该节点。如果没有出现过，则将该节点加入到哈希集合中，并更新指针的位置。最后，返回链表的头节点。

至此，我们已经完成了使用Golang来删除链表中重复元素的操作。无论是有序链表还是无序链表，我们都可以通过相应的算法实现删除的功能。希望本文对您的学习和工作有所帮助！