推 mpyh12345: 大師晚安 01/07 00:09
→ heynui: 大師 01/07 00:09
→ holebro: 快慢指針 寫到變反射了 01/07 00:10
→ sustainer123: 還好我有特別去學 不然這題一定寫不出來 01/07 00:11
推 SecondRun: 大師 01/07 00:27
142. Linked List Cycle II
給定一個linked list，如果存在循環，回傳循環開始的node；無循環則回傳Null。
如果串列中有存在一些節點可以藉由一直跟著指標 next 走而重複抵達的話，則代表該連
結串列中有環。測資中，pos 將代表尾端連結到的連結串列中之位置（索引值從 0 開始
）。如果 pos 為 -1 ，則連結串列中無環。注意到，pos 實際上並不會作為參數傳入。
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the
second node.
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the
first node.
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
思路:
又是使用fast & slow pointer的題目。
為了避免出現空指標，先設定fast與fast->next不為NULL，之後開始跑迴圈，
找到slow == fast即可跳出迴圈。
第二步確認是否有循環，如無循環，回傳NULL。
最後，使head跑到與slow的交會處，此處即為循環起始點，回傳head。
C Code
----------------------
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast = head;
struct ListNode *slow = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
break;
}
}
if(fast == NULL || fast->next == NULL) return NULL;
while( head != slow ){
head = head->next;
slow = slow->next;
}
return head;
}
-------------------
補記:
最多人觀看的解答滿猛的，不過我看不太懂他的想法，明天再研究。
晚安
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.115.119 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673021317.A.11E.html
※ 編輯: sustainer123 (223.137.115.119 臺灣), 01/07/2023 00:10:35