Go中怎么遍歷環(huán)形鏈表

在Go中遍歷環(huán)形鏈表可以通過(guò)兩種方法實(shí)現(xiàn)：

1. 快慢指針?lè)ǎ菏褂脙蓚€(gè)指針，一個(gè)慢指針每次移動(dòng)一步，一個(gè)快指針每次移動(dòng)兩步。如果鏈表中有環(huán)，那么這兩個(gè)指針最終會(huì)相遇。具體實(shí)現(xiàn)代碼如下：

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        if slow == fast {
            return true
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}

2. 標(biāo)記法：遍歷鏈表時(shí)，給每個(gè)節(jié)點(diǎn)一個(gè)標(biāo)記，如果發(fā)現(xiàn)已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，則說(shuō)明鏈表有環(huán)。具體實(shí)現(xiàn)代碼如下：

type ListNode struct {
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    cur := head
    for cur != nil {
        if cur.Val == -1 {
            return true
        }
        cur.Val = -1
        cur = cur.Next
    }
    return false
}