給定一個(gè)鏈表，判斷該鏈表中是否存在環(huán)。

設(shè)環(huán)的長(zhǎng)度為 R，快指針比滿指針總多走一步。
當(dāng)慢指針 slow 走到環(huán)入口時(shí)，快指針 fast 在環(huán)內(nèi)，設(shè)二者之間的距離為S。在慢指針進(jìn)入環(huán)后的 t 時(shí)間內(nèi)，快指針從距離環(huán)入口 S 處走了 2t 個(gè)節(jié)點(diǎn)，相當(dāng)于從環(huán)入口走了 S+2t 個(gè)節(jié)點(diǎn)。而此時(shí)慢指針從環(huán)入口走了 t 個(gè)節(jié)點(diǎn)。

假設(shè)：快、慢指針一定可以相遇，那么有 S+2t?t=nR，即 S+t=nR。對(duì)于任意的S、R、n，總可以找到一個(gè) t 滿足上式，那么就可以說明快慢指針一定可以相遇。
所以如果鏈表中有環(huán)，那么當(dāng)慢指針進(jìn)入到環(huán)時(shí)，在未來的某一時(shí)刻，快、慢指針一定可以相遇，通過這個(gè)也就可以判斷鏈表是否有環(huán)。

注意：實(shí)際上，由于 S<R，所以在慢指針走過一圈之前就可以相遇。

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = Noneclass Solution(object):def hasCycle(self, head):""":type head: ListNode:rtype: bool"""slow = headfast = headwhile fast and fast.next and fast.next.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False

參考鏈接：https://blog.csdn.net/sinat_35261315/article/details/79205157

總結(jié)

以上是生活随笔為你收集整理的24/100. Linked List Cycle的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。