【本文鏈接】
http://www.cnblogs.com/hellogiser/p/linked-list-loop-and-intersections.html
(1)鏈表是否有環?
設置兩個指針(fast, slow)，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環，則fast必定先進入環，而slow後進入環，兩個指針必定相遇，設碰撞點為p。(當然，fast如果為NULL，則為無環鏈表)程序如下：
【代碼】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
bool IsExitsLoop(slist *head)
{
slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break;
}
if (fast == NULL || fast->next == NULL)
return false;
return true;
}
(2)找到環的入口點？
定理：slow和fast相遇點為p，讓slow從head開始，fast從p開始，每次往後各走一步，直到slow和fast再次相遇，則相遇點即為環的入口。
證明：
當fast若與slow相遇時，slow肯定沒有走遍歷完鏈表，而fast已經在環內循環了n圈(n>=1)。假設slow走了s步，則fast走了2s步（fast步數還等於s 加上在環上多轉的n圈），設環長為r，則：
2s = s + nr 即：s= nr
設整個鏈表長L，環入口與相遇點距離為x，起點到環入口點的距離為a。
則s=a+x, L=a+r。那麼a + x = nr = (n – 1)r +r = (n-1)r + L - a，則有a = (n-1)r + (L – a – x)。
(L–a–x)為相遇點到環入口點的距離，由此可知，從鏈表頭到環入口點等於(n-1)循環內環+相遇點到環入口點，於是我們從鏈表頭、相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇第一點為環入口點。
【代碼】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
slist *FindLoopPort(slist *head)
{
slist *slow = head, *fast = 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;
}
(3)如何知道環的長度？
記錄下碰撞點meet，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度r。
【代碼】
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/30
*/
unsigned int GetLoopLength(slist *head)
{
slist *slow = head, *fast = head;
while ( fast && fast->next )
{
slow = slow->next;
fast = fast->next->next;
if ( slow == fast ) break;
}
if (fast == NULL || fast->next == NULL)
return 0;
slist *meet = slow;
slow = meet->next;
fast = meet->next->next;
unsigned int len = 1;
while (slow != fast)
{
len ++;
slow = slow->next;
fast = fast->next->next;
}
return len;
}
(4)帶環鏈表的長度是多少？
L=a+r。
(5)判斷兩個單鏈表是否相交？
判斷兩個單鏈表是否相交，如果相交，給出相交的第一個點（兩個鏈表都不存在環）。
比較好的方法有兩個：
一、將其中一個鏈表L2首尾相連，檢測另外一個鏈表L1是否存在環，如果存在，則兩個鏈表相交，而檢測出來的依賴環入口即為相交的第一個點。
二、如果兩個鏈表相交，那個兩個鏈表從相交點到鏈表結束都是相同的節點，我們可以先遍歷一個鏈表，直到尾部，再遍歷另外一個鏈表，如果也可以走到同樣的結尾點，則兩個鏈表相交。這時我們記下兩個鏈表length，再遍歷一次，長鏈表節點先出發前進(lengthMax-lengthMin)步，之後兩個鏈表同時前進，每次一步，相遇的第一點即為兩個鏈表相交的第一個點。具體參見35.兩鏈表的第一個公共結點[Find the first common node of two linked list]。
【參考】
http://www.cnblogs.com/hellogiser/p/find-the-first-common-node-of-two-linked-list.html
http://www.cppblog.com/humanchao/archive/2012/11/12/47357.html
http://blog.csdn.net/liuxialong/article/details/6555850
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/linked-list-loop-and-intersections.html
