溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。
說明：不允許修改給定的鏈表。
代碼實現:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *low = head;
ListNode *fast = head;
ListNode *meet = NULL;
while(fast)
{
fast = fast->next;
low = low->next;
if(!fast)
return NULL;
fast = fast->next;
if(low == fast)
{
meet = fast;
break;
}
}
if(meet == NULL)
return NULL;
while(head && meet) //head和meet到達一定相同的步數會在環的起始點相遇
{
if(head == meet)
{
return head;
}
head = head->next;
meet = meet->next;
}
return NULL;
}
};
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
