雙指標是演算法中非常重要的一個解決問題的思路，
雙指標顧名思義，就是有兩個指標，根據雙指標的方向及速度，我們一般將雙指標分為以下幾種場景
1、快慢雙指標
2、左右雙指標
所謂快慢雙指標是指，兩個指標，一個快指標，一個慢指標，按照相同的方向，從鏈表（或陣列）的一側移動到另外一側的場景，
如下圖：
而左右雙指標，是指兩個指標，分別指向鏈表的左右兩側，相向而行，
如下圖：
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 }
如果你覺得寫的不錯，歡迎轉載和點贊， 轉載時請保留作者署名jilodream/王若伊_恩賜解脫（博客鏈接：http://www.cnblogs.com/jilodream/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/505515.html
標籤：其他