用快慢指針判斷單連結清單環，找到環入口 擴充到判斷兩個連結清單是否相交

快慢指針在解決單連結清單環問題的時候是非常有用的，下面來探讨一下單連結清單的環的一些問題。

有一個單連結清單，其中可能有一個環，也就是某個節點的next指向的是連結清單中在它之前的節點，這樣在連結清單的尾部形成一環。

問題：

1. 如何判斷一個連結清單是不是這類連結清單？
2. 如果連結清單為存在環，如果找到環的入口點？

判斷連結清單是否存在環

設定兩個指針(fast, slow)，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果連結清單存在環，則fast必定先進入環，而slow後進入環，兩個指針必定相遇。(當然，fast先行頭到尾部為NULL，則為無環連結清單)程式如下：

int isExitsLoop(LinkList L) {
    LinkList fast, slow;
    fast = slow = L;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            break;
        }
    }
    return ((fast == NULL) || (fast->next == NULL));
}
           

找到環的入口點

當fast若與slow相遇時，slow肯定沒有走周遊完連結清單，而fast已經在環内循環了n圈(1<=n)。假設slow走了s步，則fast走了2s步（fast步數還等于s 加上在環上多轉的n圈），設環長為r，則：

        2s = s + nr         s= nr

設整個連結清單長L，入口環與相遇點距離為x，起點到環入口點的距離為a。

a + x = nr

      a + x = (n – 1)r +r = (n-1)r + L - a

      a = (n-1)r + (L – a – x)

(L – a – x)為相遇點到環入口點的距離，由此可知，從連結清單頭到環入口點等于(n-1)循環内環+相遇點到環入口點，于是我們從連結清單頭、與相遇點分别設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環入口點。程式描述如下：

node* findLoopPort(node *head) {
    node *fast, *slow;
    fast = slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            break;
        }
    }
    if ((fast == NULL) || (fast->next == NULL)) {
        return NULL;
    }
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}
           

擴充問題：

判斷兩個單連結清單是否相交，如果相交，給出相交的第一個點（兩個連結清單都不存在環）。

比較好的方法有兩個：

1. 将其中一個連結清單首尾相連，檢測另外一個連結清單是否存在環，如果存在，則兩個連結清單相交，而檢測出來的依賴環入口即為相交的第一個點。
2. 如果兩個連結清單相交，那個兩個連結清單從相交點到連結清單結束都是相同的節點，我們可以先周遊一個連結清單，直到尾部，再周遊另外一個連結清單，如果也可以走到同樣的結尾點，則兩個連結清單相交。

這時我們記下兩個連結清單length，再周遊一次，長連結清單節點先出發前進(lengthMax-lengthMin)步，之後兩個連結清單同時前進，每次一步，相遇的第一點即為兩個連結清單相交的第一個點。