給定一個鏈表，回傳鏈表開始入環的第一個節點， 如果鏈表無環，則回傳 null，
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，注意，pos 僅僅是用于標識環的情況，并不會作為引數傳遞到函式中， 說明：不允許修改給定的鏈表，
解題思路：
1.使用快慢指標判斷有無環：讓慢指標每次走一步，快指標每次走倆步，
不理解為什么快慢指標可以來判斷有無環的可以看上一篇博客：
環形鏈表1
slow = slow->next;
fast = fast->next->next;
2.當有環時：fast與slow會相遇，再讓頭結點head與相遇結點fast一起每次走一步，
head與fast相遇時，就是環的第一個結點，
如下圖所示：
A為鏈表頭結點的位置，B為入環結點的位置，C為快慢指標相遇位置，
設AB=L，BC=X，圓環周長為R，
CB=R-C
當快慢指標相遇時：慢指標slow的路程為L+X
快指標為L+X+nR
根據快指標走的路程時慢指標走的二倍：
2(L+X) = L+X+nR
化解得：L = n*R-X
L = (n-1)R + (R-X)
代碼實作：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
//創建快慢指標slow，fast
struct ListNode* slow = head,*fast = head;
//判斷是否有環
while(fast && fast->next)
{
slow = slow->next;//慢指標每次走一步
fast = fast->next->next;//快指標每次走倆步
if(fast == slow)
{
break;//相遇跳出
}
}
if(fast == NULL || fast->next == NULL)//判斷無環的情況
{
return NULL;
}
//有環
while(head != fast)//fast從與slow相遇的結點走，head從頭開始走，head與fast相遇點就是環的頭結點
{
head = head->next;
fast = fast->next;
}
return head;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/240842.html
標籤：其他
上一篇：指標和陣列學習筆記1