Golang 检测链表中的循环

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

方法1：使用双指针方法

在这种方法中，使用一个低指针和一个高指针来遍历链表。高指针每次前进两步，低指针每次前进一步。如果链表中包含循环，高指针最终会追上低指针，并且它们都指向同一个节点。在这种情况下，我们返回真。

步骤

第1步 －在程序中创建一个main包，并声明fmt（格式化包）包，该包用于产生可执行的代码和格式化输入和输出。
第2步 －创建一个节点结构体，值的类型为int，Next的类型为Node。
第3步 －创建一个函数has_loop，在该函数中创建两个指针low和high，并将它们都指向链表的头节点。
第4步 －高指针每次移动两步，低指针每次移动一步。
第5步 －在包含循环的链表中，高指针最终会追上低指针，它们会指向同一个节点。
第6步 －在这种情况下返回真，因为链表包含循环。
第7步 －如果链表没有循环，快指针最终会到达链表的末尾，此时我们可以返回假。
第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中的Maps

在这个实现中，我们使用一个map来记录访问过的节点。对于链表中的每个节点，我们确定它之前是否已经被访问过。如果是，则返回true，因为链表包含一个循环。如果在到达链表末尾之前没有遇到访问过的节点，则返回false。

步骤

步骤1 - 在程序中创建一个名为main的package，并声明fmt（格式化包）package。main package用于生成可执行的代码，fmt package用于格式化输入和输出。
步骤2 - 创建一个Node struct，其中value的类型为int，Next的类型为Node。
步骤3 - 创建一个has_loop函数，并在该函数中创建一个map来存储已访问的节点。
步骤4 - 当遍历链表时，检查每个节点，从头节点开始。
步骤5 - 验证每个节点在map中的存在，以确定它之前是否已经被访问过。
步骤6 - 如果一个节点之前已经被访问过，则返回true，因为链表有一个循环。
步骤7 - 当到达链表末尾时，如果没有访问过的节点，则返回false。
步骤8 - 这种方法使用map来存储访问过的节点，时间复杂度为O(n)，空间复杂度为O(n)，其中n是链表中节点的数量。

示例

在这个示例中，我们将使用map来存储访问过的节点。

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
}