Re: [閒聊] 每日LeetCode
142. Linked List Cycle II
給一個 linked list 的 head，
若是最尾端節點接回中間的某個節點形成環則回傳這個節點，
否則回傳 null。
規定: 不要修改 linked list 上的值
額外挑戰: 只使用 O(1) 的 memory
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation:
https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png
最後一個節點接回 index = pos 的節點 (pos 實際上我們一開始不知道是多少)
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation:
https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation:
只有一個點且沒形成自環
方法一 (space O(N)):
用一個 set 把走過的點存起來，
如果下一個是已經走過的點代表形成環了，回傳這個點，
如果走到末端了還沒遇到任何走過的點代表這個 list 上沒有環。
C++ code:
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*> st;
st.insert(head);
ListNode *p = head;
while(p){
if(st.find(p->next) != st.end()) return p->next;
st.insert(p->next);
p = p->next;
}
return NULL;
}
};
---
方法二 (space O(1)):
使用快慢指標 (Floyd cycle detection algorithm) 來尋找，
其中一個指標 (快指標) 從 head 開始每回合移動 2 步，
另外一個指標 (慢指標) 從 head 開始每回合移動 1 步，
若是沒有環則快指標會在 N/2 回合後碰到 null，
若是有環則他們倆最慢一定會在 2N 回合內在環上的某個點相遇。
我們假設他們在 a+b 回合後碰到，其中 a 是從 head 走到環上所需的回合數，
快指標總共移動了 2(a+b) 步，慢指標移動了 (a+b) 步，
假設環的大小為 m，
當他們相遇時，快指標比慢指標多移動了 c*m 步 (c 是正整數)，
由此可得此等式: 2(a+b) - (a+b) = c*m，
透過移項得到: a+b = c*m，
這代表慢指標移動了 a+b 步剛好是 m 的倍數，
並且再移動 a 步則可以走到環的進入點 (a + c*m)。
因此我們利用另外一個指標從 head 出發，慢指標則從快慢指標的相遇點出發，
他們每回合都同樣移動一步，最後會在環的進入點相遇。
C++ code:
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head) return NULL;
ListNode *fast = head, *slow = head;
while(fast->next && fast->next->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow) break;
}
if(!(fast->next && fast->next->next)) return NULL;
while(head != slow){
head = head->next;
slow = slow->next;
}
return head;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1678327579.A.95E.html
※ 編輯: idiont (140.113.229.216 臺灣), 03/09/2023 11:19:23
推
03/09 12:35,
2年前
, 1F
03/09 12:35, 1F
推
03/09 16:32,
2年前
, 2F
03/09 16:32, 2F
討論串 (同標題文章)
完整討論串 (本文為第 263 之 719 篇)：