目錄：
- 1.帶環問題(判斷是否帶環)
- (1)題目描述
- (2)思路決議
- a.問題： 怎么證明快指標和慢指標一定會在環里相遇，而不是一直錯過?
- b.問題：如果slow一次走一步，fast一次走3步？fast一次走4步？fast一次走n步？能追上嗎？
- (3)代碼實作
- 2.帶環問題(回傳入環點)
- (1)題目描述
- (2)思路決議
- (3)代碼實作
1.帶環問題(判斷是否帶環)
(1)題目描述
給定一個鏈表，判斷鏈表中是否有環
如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環， 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意：pos 不作為引數進行傳遞，僅僅是為了標識鏈表的實際情況，
如果鏈表中存在環，則回傳 true ， 否則，回傳 false ，
示例1
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點，
示例2
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環，
使用語言： C語言
(2)思路決議
此題可以用快慢指標解決，給兩個指標分別指向鏈表的頭節點，慢指標走一個節點快指標走兩個節點，當快指標為慷訓快指標的next為空，則不帶環，若快指標指向和慢指標直指向的同一位置，則證明此鏈表帶環，且二者必在環里相遇
a.問題： 怎么證明快指標和慢指標一定會在環里相遇，而不是一直錯過?
b.問題：如果slow一次走一步，fast一次走3步？fast一次走4步？fast一次走n步？能追上嗎？
結論：不一定能追上
如果slow一次走一步，fast一次走3步，它們之間的差距就是
n-2
n-4
n-6
…
如果差距是0就追上了，相當于slow在原地不動，fast每次走兩步，以減小兩者之間的差距，那么說明如果n是偶數，就能追上，n是奇書就會錯過，最特殊的情況錯過之后，差距還是奇數，那么就會永遠追不上
如果fast每次走4/5/…/n步是同樣的道理
(3)代碼實作
bool hasCycle(struct ListNode *head)
{
struct ListNode * slow = head;
struct ListNode * fast = head;
//若fast或fast->next為空不帶環
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
//若兩個指標指向同一位置，則代換
if(fast == slow)
return true;
}
return false;
}
2.帶環問題(回傳入環點)
(1)題目描述
給定一個鏈表，回傳鏈表開始入環的第一個節點， 如果鏈表無環，則回傳 NULL
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意，pos 僅僅是用于標識環的情況，并不會作為引數傳遞到函式中，
說明：不允許修改給定的鏈表，
示例1
輸入：head = [3,2,0,-4], pos = 1
輸出：回傳索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點，
示例2
輸入：head = [1], pos = -1
輸出：回傳 null
解釋：鏈表中沒有環，
使用語言: C語言
(2)思路決議
給兩個指標分別指向鏈表的頭節點，慢指標走一個節點快指標走兩個節點，當快指標為慷訓快指標的next為空，則不帶環，若快指標指向和慢指標直指向的同一位置，則證明此鏈表帶環，且二者必在環里相遇，保存兩個指標相遇的位置到給指標meet，此時meet位置距離入環節點的位置剛好等于head到入環節點的位置，此時只需讓meet和head同時走，二者相遇的位置就是入環節點的位置
圖解如下：
(3)代碼實作
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode * fast = head;
struct ListNode * slow = head;
//先判斷是否帶環
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
//相遇的節點給meet
struct ListNode * meet = slow;
//帶環，給兩個指標一個head一個meet，兩個指標同時走，直到相遇，相遇點就是入環的節點
while(meet != head)
{
head = head->next;
meet = meet->next;
}
return head;
}
}
return NULL;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255966.html
標籤：其他
上一篇：HSC490控制器除錯筆記（一）