不論在面試或者刷題程序中，很大概率都會遇到環形鏈表這種型別的題目，例如 leetcode 141. 環形鏈表 以及 leetcode 142. 環形鏈表 II 等，本文主要介紹通過快慢指標法來解決此類題型，以供大家參考，
環形鏈表
環形鏈表大致樣子如下圖所示：
快慢指標法
判斷鏈表是否是環形鏈表，一般通過快慢指標法，
操作步驟
一、分別定義兩個均指向頭節點的指標（fast/slow）；
二、快指標每次走兩步，慢指標每次走一步；
三、如果鏈表存在環，則快慢指標一定會在環中相遇，
如下圖示，快慢指標行走的軌跡如下：
faster： 1--->3--->5--->7
slower：1--->2--->3--->4
faster： 7--->5
slower：4--->5
當他們同時到達節點 5 時，完美相遇，
舉栗1：判斷鏈表是否有環
題目
Show me the Code
舉例2：求入環的第一個節點
題目
思路
本題除了需要判斷鏈表是否有環外，如果有環還要求入環的第一個節點，因此是上一個題目的升級版本，還是以快慢指標中舉例的那個鏈表作為示例，下圖將描述當鏈表有環的時候，如何求出入環的第一個節點，見下圖示：
已判斷鏈表有環
求入環的第一個節點
讓慢指標重新指向鏈表的頭節點，并讓快慢指標同時每次只走一步
faster：5--->6--->7
slower：1--->2--->3
繼續走
faster：7--->4
slower：3--->4
當他們同時到達節點 4 時，再次完美相遇，
因此，由上面的圖可知，當判斷鏈表有環（快慢指標相遇）之后，再讓快（或者慢）指標重新指向鏈表頭節點，另外一個指標仍保持指向不變，然后讓快/慢指標同時走，且每次只走一步，當他們再次相遇時，此時相遇的節點就是入環的第一個節點，
Show me the Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260505.html
標籤：其他
上一篇：docker07-資料存盤
下一篇：Transformer