題目描述
給定一個鏈表肝谭，判斷鏈表中是否有環(huán)傻丝。
進(jìn)階:
你能否不使用額外空間解決此題拢切？
解題思路
- 無環(huán)鏈表，最后一個節(jié)點為nil同欠，有環(huán)鏈表可以無限循環(huán)next下去
- 不用額外空間：快慢節(jié)點，慢節(jié)點一次走一步横缔，快節(jié)點一次走兩步铺遂，當(dāng)進(jìn)入環(huán)中，每次循環(huán)茎刚，快節(jié)點會離慢節(jié)點近一步襟锐，快節(jié)點最終會追上慢節(jié)點
- 用額外空間： 用map存走過的節(jié)點，第一個走過的節(jié)點就是環(huán)的入口
代碼實現(xiàn)
// ListNode Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func hasCycle(head *ListNode) bool {
if head != nil {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
return true
}
}
}
return false
}
GitHub
- 源碼傳送門
- 項目中會提供各種數(shù)據(jù)結(jié)構(gòu)及算法的Golang實現(xiàn), LeetCode解題思路及答案
