数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Go语言程序检测链表循环
在Go语言数据结构中，链表包含包含两个字段的节点：下一个指针和链表的数据。我们将使用两种方法来检测链表中的循环。第一种方法将使用双指针法，第二个例子使用映射来执行程序。让我们来看这些例子来理解执行过程。
方法一：使用双指针法
在这种方法中，使用慢指针和快指针遍历链表。快指针一次前进两步，慢指针一次前进一步。如果链表包含循环，快指针最终将超过慢指针，它们都将指向同一个节点。在这种情况下，因为链表包含循环，所以我们返回true。
算法
步骤1 − 创建一个名为main的包，并在程序中声明fmt（格式化包），其中main产生可执行代码，fmt帮助格式化输入和输出。
步骤2 − 创建一个Node结构体，其值为int类型，Next为Node类型。
步骤3 − 创建一个函数has_loop，并在该函数中创建两个指针——low和high——并将它们都设置为指向链表的头。
步骤4 − 快指针一次移动两步，而慢指针一次移动一步。
步骤5 − 在包含循环的链表中，快指针最终将超过慢指针，然后两个指针都将指向同一个节点。
步骤6 − 在这种情况下返回true，因为链表包含循环。
步骤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
方法二：在Go语言中使用映射
在此实现中，已访问的节点记录在一个映射中。我们检查链表中的每个节点是否之前已访问过。如果访问过，则返回true，因为链表包含循环。如果我们到达链表的末尾而没有遇到已访问的节点，则返回false。
算法
步骤1 − 创建一个名为main的包，并在程序中声明fmt（格式化包），其中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
结论
我们使用两种方法执行了检测链表中是否存在循环的程序。在第一种方法中，我们使用了双指针法，在第二个例子中，我们使用了映射来存储已访问的节点。
503 次浏览
