我們昨天使用到了雙向BFS，其實還有一種類似的技巧，稱為雙指標．一般來說的演算法使用一個指標(這個指標不是指記憶體那個，而是指在遍歷過程中的位置)，而雙指標就是同時使用兩個指標，主要分成以下兩種

1.快慢指標：有一組一快一慢的指標，主要是用來解決LinkedList的問題，例如典型的判斷一個LinkedList是否有環

2.左右指標:有一組分成左右的指標，主要是用來解決陣列或是字串的問題，例如二分搜尋

使用快慢指標來判斷是否有環

(偷一下Leetcode的圖)

因為LinkedList的每一個節點只知道下一個節點，因此如果只有一個節點是無法判斷是否有環的．

如果LinkedList中不含有環，那最終會走到一個下一個節點為Null的情況，表示走完了．因此可以藉此判斷該LinkedList不含有環

class ListNode(val value: Int, var next: ListNode? = null)

fun hasCycle(head:ListNode?) :Boolean {
    var node = head
    while(node!=null){
        node = node.next
    }
    return false
}

但是如果這個LinkedList有環，那這段程式碼就會在while中不停循環．

所以經典的解法就是利用雙指標，一個指標跑的快，一個指標跑的慢．會發生以下兩種情形

1.這個LinkedList沒有環，最後快指標先到達了終點．

2.這個指標有環，因此快的指標跑的比慢的指標一圈後兩個相遇了(其實不一定是一圈…有可能快指標多跑了好多圈終於遇上了)有點像是小學在跑馬拉松時，前面的人領先了一圈又從後面追了上來

我們照這個思路來優化剛剛的程式碼

class ListNode(val value: Int, var next: ListNode? = null)

fun hasCycle(head: ListNode?): Boolean {
    var fast = head
    var slow = head
    while (fast != null && slow != null && fast.next != null) {//還沒有走完
        fast = fast.next?.next//快指標前進兩步
        slow = slow.next//慢指標前進一步
        if (fast == slow) {//如果有環，則兩者最終會相遇
            return true
        }
    }
    return false
}

讓我們來執行看看

fun main() {
    val node3 = ListNode(3)
    val node2 = ListNode(2)
    val node0 = ListNode(0)
    val node4 = ListNode(4)
    node3.next = node2
    node2.next = node0
    node0.next = node4
    node4.next = node2

    println(hasCycle(node3))
}

結果為true 代表上面的測試資料內有環

已知LinkedList內有環，判斷環的起點

再用一次LeetCode的圖

其中環的起點是節點2，因為從這開始打圈圈

好的，那我們如何利用找出這個節點2呢?

秘密就在上面那句”其實不一定是一圈…有可能快指標多跑了好多圈終於遇上了”，快慢節點相遇時他們之間的步數差距，一定是一圈的整數倍．

我們假設慢指標在相遇時走了k步，而我們的快指標當然走了2k步(因為我們一次讓快指標走兩步)，而兩者相減，2k-k =1k．而照上面的提示，k也是一圈的整數倍．

現在我們假設相遇點到環的起點距離是m(如果在環起點相遇的話m就是為0)，那麼從慢指標來看，從一開始的頭到環的起點，距離就是

從頭走了k步 - 相遇點到環起點的距離m = k-m

也就是說 從頭走到環起點，需要走k-m步

又 k也是一圈的整數倍，現在到相遇點走了m步，那們只要從相遇點在前進k-m步，會剛好走回環起點．

從相遇點往前走k-m步，剛好走回環的起點

因此，在相遇後，只要把其中一個指標指回頭，然後使兩個指標同速度前進．

最後相遇的地方就是k-m步，也是環的起點