快慢指针：141. 环形链表（判断是否存在环路）
題目描述
給定一個鏈表，判斷鏈表中是否有環
題目鏈接
141. 環形鏈表
解題思路
使用快慢指針（Floyd判圈算法）：從鏈表的頭部設置兩個指針，p1的步長為1， p2的步長為2，同時向前走，如果p1和p2最終能夠相遇，則說明鏈表是有環的。
檢測環的基本思想是非常簡單的，可以類比成兩個人在跑道上跑。只要有圈，跑的快的那個人就一定能夠追上跑得慢的那個人。
代碼：
public class Solution {public boolean hasCycle(ListNode head) {if (head == null) {return false;} //設置快慢指針ListNode slow = head, fast = head.next;while(slow!=null&&fast!=null&&fast.next!=null){if(slow == fast){return true;}slow = slow.next;fast = fast.next.next;}return false;} }擴展
求環的長度
兩個人相遇的是時候，一定已經在環上了，然后兩個人只要再次在環上接著跑，再次相遇的時候（也就是所謂的套圈），跑的快的那個人就比跑得慢的人整整多跑了一圈，所以環的長度也就出來了。
用算法來描述：第一次相遇后，p1和p2按照原來的步長繼續向前查找，并且記錄下兩個指針遍歷過的節點個數。當兩個指針再次相遇的時候，遍歷的節點數量差就是環的長度。
求環的起點
解決方法：
把其中的一個指針重置到鏈表頭部，然后兩個指針步長都為1，繼續向前移動，相遇的位置即為環的起點。
解釋：
首先我們設第一次相遇的時候慢指針走過的節點個數為i， 設鏈表頭部到環的起點的長度為m, 環的長度為n，相遇的位 置與起點位置距離為k。
則可以得到:
i = m + a * n + k
其中a為慢指針走的圈數。
根據快指針和慢指針的速度關系，我們可以得到另一個式子:
2 * i = m + b * n + k
其中b為快指針走的圈數。
簡單處理得到:
i = (b - a) * n
也就是說i是圈長的整數倍。
這時將其中一個節點放到起點，然后同時向前走m步時，此時從頭部走的指針在m位置。而從相遇位置開始走的指針應該在距離起點i + m, i為圈長整數倍，則該指針也應該在距離起點為m的位置，即環的起點。
參考
- Floyd判圈算法
- Floyd判圈算法
- Floyd判圈算法（龜兔賽跑算法）
總結
以上是生活随笔為你收集整理的快慢指针：141. 环形链表（判断是否存在环路）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 笔记本电脑清灰有多重要笔记本电脑清灰好处
- 下一篇： 网购女孩的抠搜小妙招，第3个绝了