資料結構
網路
關係資料庫管理系統 (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 次瀏覽
