題目描述
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點浙芙。 如果鏈表無環(huán)，則返回 null告嘲。
說明：不允許修改給定的鏈表丑勤。
進階:
你能否不使用額外空間解決此題华嘹？
解題思路
- 無環(huán)鏈表，最后一個節(jié)點為nil法竞，有環(huán)鏈表可以無限循環(huán)next下去
- 不用額外空間：快慢節(jié)點耙厚，慢節(jié)點一次走一步，快節(jié)點一次走兩步岔霸，當(dāng)進入環(huán)中薛躬，每次循環(huán)，快節(jié)點會離慢節(jié)點近一步呆细，快節(jié)點最終會追上慢節(jié)點
- 用額外空間： 用map存走過的節(jié)點型宝，第一個走過的節(jié)點就是環(huán)的入口
-
不用額外空間
環(huán)形鏈表
設(shè)：鏈表頭是X，環(huán)的第一個節(jié)點是Y絮爷，slow和fast第一次的交點是Z趴酣。各段的長度分別是a,b,c，如圖所示
第一次相遇時slow走過的距離：a+b坑夯，fast走過的距離：a+b+c+b
因為fast的速度是slow的兩倍岖寞，所以fast走的距離是slow的兩倍，有 2(a+b) = a+b+c+b柜蜈，可以得到a=c（這個結(jié)論很重要Ｕ套弧）
這時候指巡，slow從X出發(fā)，fast從Z出發(fā)隶垮，以相同速度走藻雪，同時到達Y，Y就是環(huán)的入口岁疼，即第一個節(jié)點
代碼實現(xiàn)
// ListNode Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
if head != nil {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
if slow == fast {
// X---------Y---------Z
//x起點阔涉，y環(huán)的起點，z是相遇點
//鏈表頭是X捷绒，環(huán)的第一個節(jié)點是Y瑰排，slow和fast第一次的交點是Z。各段的長度分別是a,b,c
//相遇時暖侨，fast走過的距離為 2(a+b)=a+b+c+b椭住，得到距離a=c
//則 slow從head開始走，fast從Z點開始走字逗，速度都是一次走一步京郑，slow和fast同時到達Y點，即環(huán)的入口
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
}
}
return nil
}
GitHub
- 源碼傳送門
- 項目中會提供各種數(shù)據(jù)結(jié)構(gòu)及算法的Golang實現(xiàn), LeetCode解題思路及答案
