環形鏈表
文章目錄
- 環形鏈表
- 問題一：判斷鏈表是否有環
- 問題一思路分析
- 問題二：如果相遇了，在哪相遇的
- 問題二思路分析 + 相遇點證明程序
問題一：判斷鏈表是否有環
📝題目指路：141. 環形鏈表 - 力扣（LeetCode） (leetcode-cn.com)
問題一思路分析
🎷首先題目已經給出了思路：
- 🎨如果鏈表中有某個節點，可以通過連續跟蹤
next指標再次到達，則鏈表中存在環
👞👞這就類似于追趕/追及的問題，我們經常用到的是 快慢指標👞👞
我們將上面的鏈表圖轉換為更為簡單的直觀圖
- 🎯
fast和slow兩個人賽跑 - 🎯fast先進入環
-
🎯等到
slow開始進入環的時候，開始追及問題
-
🎯假設
環的長度為C -
🎯此時
fast和slow相差C - X -
🎯而fast追slow的時候，每一步都會使得
C-X少1 -
🎯所以
最終他們會相遇 -
🎯如果他們
相遇了，證明這是個環
- 🎯如果
slow遇不到fast，fast先遇到NULL，證明這不是個環
📖📖代碼如下：
bool hasCycle(struct ListNode *head) {
struct ListNode *slow = head;
struct ListNode *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
return true;
}
}
return false;
}
問題二：如果相遇了，在哪相遇的
📝題目指路：142. 環形鏈表 II - 力扣（LeetCode） (leetcode-cn.com)
問題二思路分析 + 相遇點證明程序
先回到一開始，slow進入環，fast開始追擊的時候
📌假設 環的長度為C
📌此時fast和slow相差C - X（fast追slow）
📌設slow和fast走了t1次
📌slow的速度是1個節點/次，fast的速度是2個節點/次,
📌二者相遇之前，是fast追slow，fast和slow相差X
📌列出式子2t1 - t1 = X 又因為 t1 = L
📌得出：t1 = X = L
相遇的時候
從這里開始計時，
??設slow和fast走了t次
??slow的速度是1個節點/次，fast的速度是2個節點/次
??二者相遇之前，是fast追slow，fast和slow相差C - X
??列出式子2t - t = C - X
??得出：t = C - X
??slow走了C - X
💡從此時相遇且從此時開始我們定義一個 新指標指向鏈表起點
💡slow再開始一步一步走，直到，cur和slow地址相同，找到環形的入口
📒📒代碼如下：
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 *cur = head;
while(slow != cur)
{
cur = cur->next;
slow = slow->next;
}
return cur;
}
}
return NULL;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/339148.html
標籤：其他