Golang程序检测链接列表中的循环

在Golang的数据结构中，一个链表是包含节点的，它包含两个字段：一个下一个指针和列表的数据。我们将使用两种方法来检测链表中的循环。在第一个方法中，将使用双指针方法，在第二个例子中，使用地图来执行程序。让我们通过这些例子来了解执行情况。

方法1：使用双指针方法

在这种方法中，使用一个低指针和一个高指针来遍历链接列表。当高指针每次前进两步时，低指针每次前进一步。如果链接列表包含一个循环，高指针将最终超过低指针，并且它们都将指向同一个节点。考虑到在这个例子中链接列表包含一个循环，我们返回 true。

算法

第1步 – 创建一个包main，并在程序中声明fmt(format package)包，其中main产生可执行代码，fmt帮助格式化输入和输出。
第2步 – 创建一个Node结构，其值为int类型，Next为Node类型。
第3步– 创建一个函数has_loop，并在该函数中建立两个指针–low和high，并将它们都设置为指向链表的头部。
第4步 – 高指针每次移动两步，而低指针每次移动一步。
第5步– 在有循环的链接列表中，高指针最终会超过低指针，然后两个点都会指向同一个节点。
第6步– 在这种情况下返回真，因为链接列表包含一个循环。
第7步– 如果没有循环，快速指针将最终到达链表的末端，在这种情况下我们可以返回false。
第8步 – 使用 fmt.Println() 函数执行打印语句，其中 ln 表示新行。
第9步 – “双指针策略 “或 “龟兔赛跑算法 “是这个公式的其他名称。鉴于只需要两个指针，它的空间复杂度为O(1)，时间复杂度为O(n)，其中n是链接列表中的节点数。

例子

在这个例子中，我们将使用双指针方法来执行程序。

package main
import "fmt"

type Node struct {
   Value int
   Next  *Node
}

func has_loop(head *Node) bool {
   low := head
   high := head
   for high != nil && high.Next != nil {
      low = low.Next
      high = high.Next.Next
      if low == high {
         return true
      }
   }
   return false
}

func main() {
   head := &Node{Value: 1} //initialize the linked list with values
   node2 := &Node{Value: 2}
   node3 := &Node{Value: 3}
   node4 := &Node{Value: 4}

   head.Next = node2 //point to the elements using linked list
   node2.Next = node3
   node3.Next = node4
   node4.Next = node2

   fmt.Println("Does this linked list has loop?")
   fmt.Println(has_loop(head)) // Output: true
}

输出

Does this linked list has loop?
true

方法2：在Golang中使用地图

在这个实现中，被访问的节点被记录在一个地图上。我们确定链表中的一个节点是否在之前被访问过，对于里面的每个节点。如果有，我们就返回true，因为链接列表包含一个循环。如果我们到达链接列表的末尾而没有遇到被访问的节点，我们返回false。

算法

第1步 – 创建一个包main，并在程序中声明fmt(format package)包，其中main产生可执行代码，fmt帮助格式化输入和输出。
第2步 – 创建一个Node结构，其值为int类型，Next为Node类型。
第3步 – 创建一个函数has_loop，并在该函数中制作一个地图来存储你所访问的节点。
第4步– 当你在链表中移动时检查每个节点，从头部开始。
第5步– 验证每个节点在地图上的存在，看它以前是否被访问过。
第6步 – 如果一个节点以前被访问过，则返回true，因为链表有一个循环。
第7步– 如果当我们到达链表的末端时，没有被访问的节点，则返回false。
第8步– 这种方法采用了一个地图来存储被访问的节点，其结果是时间复杂度为O(n)，空间复杂度为O(n)，其中n是链接列表中的节点数。

例子

在这个例子中，我们将使用地图来存储访问的节点。

package main
import "fmt"

type Node struct {
   Value int
   Next  *Node
}

func has_loop(head *Node) bool {
   Map := make(map[*Node]bool)  //create a map to store visited nodes.
   for current := head; current != nil; current = current.Next {
      if Map[current] {
         return true
      }
      Map[current] = true
   }
   return false
}

func main() {
   head := &Node{Value: 10}   //fill the linked list with elements 
   node2 := &Node{Value: 20}
   node3 := &Node{Value: 30}
   node4 := &Node{Value: 40}

   head.Next = node2 
   node2.Next = node3
   node3.Next = node4
   node4.Next = node2
   fmt.Println("Does this linked list has loop?")

   fmt.Println(has_loop(head)) // Output: true
}

输出

Does this linked list has loop?
true

结论

我们用两种方法执行了检测链接列表中是否有循环的程序。在第一种方法中，我们使用了双指针方法，在第二个例子中，我们使用地图来存储被访问的节点。

Golang程序 检测链接列表中的循环

方法1：使用双指针方法

算法

例子

输出

方法2：在Golang中使用地图

算法

例子

输出

结论

Golang程序检测链接列表中的循环