[閒聊] LeetCode 142

作者: sustainer123 (caster)   2023-01-07 00:08:33
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
作者: mpyh12345 (嘉義金城武)   2023-01-07 00:09:00
大師晚安
作者: heynui (天音かなた的兔)   2023-01-07 00:09:00
大師
作者: holebro (穴弟弟)   2023-01-07 00:10:00
快慢指針 寫到變反射了
作者: sustainer123 (caster)   2023-01-07 00:11:00
還好我有特別去學 不然這題一定寫不出來
作者: SecondRun (雨夜琴聲)   2023-01-07 00:27:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com