題目要求
??給定一個鏈表，判斷鏈表中是否有環，如果鏈表中有某個節點，可以通過連續跟蹤 next 指標再次到達，則鏈表中存在環， 如果鏈表中存在環，則回傳入環的結點 ， 否則，回傳NULL，
思路
??設定快慢指標，快指標一次走兩步，慢指標一次走一步，如果有環，快慢指標同時進環后，快指標會追上慢指標，他們的地址會相等，然后，從快慢指標相遇處和鏈表的頭結點處，分別出發兩個指標，均走一步，兩個指標會在入環處相遇，回傳該結點即可，
圖解
代碼實作
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode * fast = head;
struct ListNode * slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
struct ListNode* slowHead = head;
while (slow != slowHead)
{
slow = slow->next;
slowHead = slowHead->next;
}
return slow;
}
}
return NULL;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/255983.html
標籤：其他
上一篇：C語言 qsort函式及其實作