淺談雙指標技巧（一）---通過雙指標判斷連結串列成環問題

雙指標是演演算法中非常重要的一個解決問題的思路。
雙指標顧名思義，就是有兩個指標。根據雙指標的方向及速度，我們一般將雙指標分為以下幾種場景
1、快慢雙指標
2、左右雙指標
所謂快慢雙指標是指，兩個指標，一個快指標，一個慢指標，按照相同的方向，從連結串列（或陣列）的一側移動到另外一側的場景。

如下圖：

而左右雙指標，是指兩個指標，分別指向連結串列的左右兩側，相向而行。

如下圖：

快慢雙指標一般用於查詢連結串列成環、特殊位置的節點、滑動視窗等問題。

左右雙指標一般是解決二分查詢等問題
雖然都歸結為雙指標，但其實他們的思想各不相同，甚至不同場景的問題，思想都不同，只是由於都用到了兩個指標，將這類演演算法技巧統稱為雙指標。
本文我們重點來看快慢雙指標的經典問題：(防盜連線：本文首發自http://www.cnblogs.com/jilodream/ )
判斷連結串列是否成環
力扣 141. 環形連結串列 （https://leetcode.cn/problems/linked-list-cycle/）
給你一個連結串列的頭節點 head ，判斷連結串列中是否有環。
所謂的連結串列存在環，也就是下邊這個樣子，沒有某個節點的next指向null：

這個場景，如果環的結構不大的話，我們可以直接將結果直接存放到一張hash表中，然後指標從頭部依次遍歷，判斷新指向的節點是否已經存在於hash表中。

如果hash表中存在，則判定為當前連結串列存在環，否則將該節點加入到hash表中，繼續遍歷。直到遇到連結串列的尾結點（next指標指向null）時，判定為不存在環。
這種思想的程式碼這裡就不寫了。(防盜連線：本文首發自http://www.cnblogs.com/jilodream/ )
如果資料規模小的話，這個辦法沒有問題，甚至會很快。但是如果資料規模很大的話，這就會導致沒有足夠的記憶體來存放這個hash表。
如果不採用臨時快取的辦法，那麼應該咋麼解決呢？來看看快慢雙指標的思路
快指標Fast、慢指標Low，同時指向頭結點，然後均向像隊尾移動，區別是快指標每次移動兩個節點，慢指標每次移動一個節點。
如果連結串列不存在環，那麼經過不斷的移動，快指標肯定會找到隊尾元素。
如下圖 ：

這裡很好理解。
如果連結串列存在環，那麼經過不斷的移動，快慢指標最終會相遇，同時指向某個節點。
如下圖：

這是為什麼呢？快指標再次跨過慢指標我們可以理解，為什麼會恰好相遇在某個節點，而不是每次都恰好越過慢指標呢？

答案是並不會，原因是：(防盜連線：本文首發自http://www.cnblogs.com/jilodream/ )
快慢指標經過移動後，同時處在環中，假設快指標通過由於速度快，再次趕上慢指標的節點差距為N。由於快指標每次比慢指標快一步，導致N每次逐漸縮小1，因此這個N=1。
感興趣的讀者可以自己在紙上畫一下。
下面我們直接來看程式碼

 1     public boolean hasCycle(ListNode head) {
 2         if (head == null) {
 3             return false;
 4         }
 5         ListNode fast = head;
 6         ListNode low = head;
 7         while (true) {
 8             if (fast == null) {
 9                 return false;
10             }
11             if (fast.next == null) {
12                 return false;
13             }
14             if (fast.next.next == null) {
15                 return false;
16             }
17             fast = fast.next.next;
18             low = low.next;
19             if (fast == low) {
20                 return true;
21             }
22         }
23     }