注：詳細代碼到https://github.com/go-snail/arithmetic/tree/master/link下載援奢。
鏈表中環(huán)的監(jiān)測
1、判斷是否存在環(huán)
通過快慢指針方式哄尔。slow和fast叶洞，初始化slow=fast=head鳖擒，循環(huán)執(zhí)行以下操作slow = slow.next,fast = fast.next.next,判斷slow == fast粘驰，若slow == fast烤黍，記交點為p漠吻，則存在環(huán)赵誓，否則不存在打毛。
2、求取環(huán)的長度
從p開始執(zhí)行以下操作slow=slow.next,fast=fast.next,再次相交時俩功，執(zhí)行的操作數(shù)幻枉，即為環(huán)的長度。
3诡蜓、找出環(huán)的連接點
如果單鏈表有環(huán)熬甫，按照方法二的思路，走得快的指針fast若與走的慢的指針slow相遇時蔓罚，slow指針肯定沒有遍歷完鏈表椿肩，而fast指針已經(jīng)在環(huán)內(nèi)循環(huán)了n圈(n>=1)。假設(shè)slow指針走了s步豺谈，則fast指針走了2s步(fast步數(shù)還等于s加上在環(huán)上多轉(zhuǎn)的n圈)郑象，設(shè)環(huán)廠為r，則滿足如下關(guān)系表達式：
2s = s + nr 推導(dǎo)出s=nr
設(shè)整個鏈表長為L茬末，入口環(huán)與相遇點b距離為b厂榛，起點到環(huán)入口點的距離為a。則滿足如下關(guān)系表達式：
r = L-a
a+b = s = nr = (n-1)*r+r = (n-1)*r+L-a 推導(dǎo)出a = (n-1)r+(L-a-b)
如上面的圖可得知丽惭，L-a-b為相遇點b到環(huán)入口點的距離击奶，從鏈表頭到環(huán)入口點a的距離a等于n-1循環(huán)內(nèi)環(huán)+相遇點到環(huán)入口點的距離。于是從鏈表頭與相遇點分別設(shè)一個指針责掏，每次各走一步正歼，兩個指針必定相遇，且相遇第一點為環(huán)的入口點拷橘。
編碼如下：
type chainNodestruct {
????num????int
? ? next *chainNode
}
var gc =make(map[*chainNode]int, 0)
func NewChainNode() *chainNode {
????return &chainNode{0, nil}
}
func (l *chainNode)ListChain() {
????for l.next != nil && gc[l.next] ==0 {
????gc[l.next] =1
? ? ?fmt.Printf(" %d", l.next.num)
????l = l.next
????}
}
func (pHead *chainNode)CreateChain() {
var temp *chainNode
var a *chainNode
for i :=1; i <=7; i++ {
temp = NewChainNode()
temp.num = i
pHead.next = temp
pHead = pHead.next
if i ==4 {
a = temp
}
}
temp.next = a
}
func (pHead *chainNode)Checkloop()? {
var fast =? pHead.next
var slow = pHead.next
slow = slow.next
fast = fast.next.next
for slow != fast && fast != nil && slow != nil {
fast = fast.next.next
slow = slow.next
}
fmt.Println("交點b:", fast.num)
slow = slow.next
len1 :=1
? //fast不動局义，slow繼續(xù)走再次相等則為環(huán)的長度
? for slow != fast {
slow = slow.next
len1++
}
fmt.Println("This length of cycle is:", len1)
//求長度
? len2 :=0
? slow = pHead.next
for slow != fast {
fast = fast.next
slow = slow.next
len2 ++
}
fmt.Println("This length of chain is:", len1 + len2)
}
