單鏈表的帶環問題
- 判斷單鏈表中是否存在環
- 1.問題分析
- 2.代碼實作
- 若帶環，求環的長度
- 1.問題分析
- 2.代碼實作
- 若帶環，求環的連接點
- 問題分析
- 2.代碼實作
判斷單鏈表中是否存在環
1.問題分析
（1）不帶環的鏈表的最后一個結點的next指標是指向NULL，而帶環鏈表沒有類似的最后節點，所以無法判斷帶環鏈表的結束，也就無法通過遍歷一遍鏈表來求取鏈表的長度，但是如果有一個指標在遍歷時它最后會一直在環中重復打圈，因此我們可以使用快慢指標來判斷(fast / slow)，如果鏈表帶環那么當fast走到空指標時slow還未走到，他們不會相遇；當鏈表帶環，那么當fast在環中一定會和slow相遇，
（2）慢指標slow向前一步，快指標fast應該向前幾步呢？我們需要仔細分析，
情況一
假設慢指標走一步，快指標走兩步：當slow剛要進環時，fast和slow之間相差N個結點，每一次slow走一步，fast走兩步，fast都在追slow，并且每追一次兩者之間距離都會縮小1，最后一定會變成0（兩者相遇），
情況二
假設慢指標走一步，快指標走三步：當N為偶數時，快慢指標會第一次就相遇，當N為奇數時，第一次快慢指標會恰好錯過，這時候又分為兩種情況，
1、當環的長度為偶數時：slow和fast之間的距離又變成奇數了，所以還會恰好錯過，一直回圈，無法相交
2.當環的長度為奇數時：slow和fast之間的距離變為偶數，則下次兩者一定會相遇，
其余情況都會遇到與情況二相似的問題！！
2.代碼實作
bool hasCycle(struct ListNode *head) {
struct ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}
若帶環，求環的長度
1.問題分析
在上一個問題中，我們已經求得了快慢指標相遇的點，若讓快慢指標自此從相遇點開始走，則再次相遇時，快指標比滿指標多走的長度就是環的長度，同時，由于快指標每次比慢指標多走一步，所以多走的長度 = 慢指標走的長度 = 兩個指標走的次數
2.代碼實作
int CircleLong main()
{
fast = slow = meet //先將兩個指標都定位在相遇點
int count = 0; //用于計數
while(fast != slow)
{
fast = fast->next->next;
slow = slow->next;
count++;
}
return count;
}
若帶環，求環的連接點
問題分析
由定理：相遇點meet到環連接點的距離 = 頭指標到連接點的距離，
所以我們讓兩個指標（正常指標，每次都走一步）分別從相遇點和頭指標位置走，兩個指標相遇的結點就是環的連接點， 證明如下：
2.代碼實作
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* slow = head, *fast = head; //初始化快慢指標
while(fast && fast->next) //當fast走到空，或者fast的下一個走到空，都是快指標遍歷完鏈表
{
fast = fast->next->next; //fast每次走兩步
slow = slow->next; //fast每次走一步
if(fast == slow) //相遇
{
struct ListNode* meet = fast;
while(meet != head)
{
meet = meet->next; //從相遇點開始
head = head->next; //從頭指標開始
}
return meet; //回傳連接點
}
}
return NULL; //沒有相遇回傳空指標
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/278508.html
標籤：其他
上一篇：軟體工程第四章習題