判斷循環連結清單是否有環

1. 方法一：
2.   通過快慢指針來檢查單連結清單是否存在循環
3. 判斷是否是循環連結清單時，也設定兩個指針，慢指針和快指針，讓快指針比慢指針每次移動快兩次。如果快指針追趕上慢指針，則為循環連結清單，否則不是循環連結清單，如果快指針或者慢指針指向NULL，則不是循環連結清單。
4. （1）用兩個指針p1和p2分别指向表頭結點，即p1=p2=head
5. （2）p1和p2分别采用1和2作為步長周遊該連結清單。（注意，p2應該檢查目前結點的下一個結點是否為NULL）
6. （3）如果p1或者p2遇到了NULL，則證明該連結清單沒有環；若p1和p2在某時刻指向同一結點，則說明該連結清單有環。

1. 方法二：
2. （a）p從表頭結點開始以1為步長周遊表，邊周遊邊将表反向
3. （b）如果p遇到NULL，則說明表沒有環
4. （c）如果p最後等于head，則說明表有環，且記此時p所經過的表的結點數為l（l=2l1+c，l1和c的定義見方法一）
5. （d）p再從表頭結點開始以1為步長周遊表，邊周遊邊反向，當周遊到l/2時，停止，設兩個指針p1,p2均指向目前結點，然後分别從兩個方向同時以1為步長周遊表（其中一個需要邊周遊，邊反向連結清單），當他們第相遇時，目前結點即為環頭結點。且此時連結清單還原成原來的連結清單。

給定一個單連結清單，隻給出頭指針h：

1、如何判斷是否存在環？

2、如何知道環的長度？

3、如何找出環的連接配接點在哪裡？

4、帶環連結清單的長度是多少？

解法：

1、對于問題1，使用追趕的方法，設定兩個指針slow、fast，從頭指針開始，每次分别前進1步、2步。如存在環，則兩者相遇；如不存在環，fast遇到NULL退出。

2、對于問題2，記錄下問題1的碰撞點p，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度s。

3、問題3：有定理：碰撞點p到連接配接點的距離=頭指針到連接配接點的距離，是以，分别從碰撞點、頭指針開始走，相遇的那個點就是連接配接點。

4、問題3中已經求出連接配接點距離頭指針的長度，加上問題2中求出的環的長度，二者之和就是帶環單連結清單的長度。

判斷是否存在環的程式：

?

1 2 3 4 5 6 7 8 9 10 11 12 13

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

尋找環連接配接點（入口點）的程式：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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;  }