[LeetCode] 142. Linked List Cycle II

轉自LeetCode

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up:
Can you solve it without using extra space?

<Solution>
這題是 Linked List Cycle 的衍生題

這類型的題目，其實有一個著名的演算法，叫 Floyd's Cycle Detection Algorithm

可以用來處理三個問題

(1) 判斷是否有 cycle

(2) 找到 cycle 的起始點

(3) 找出 cycle 的長度

這題可以基於 Linked List Cycle 的解法，再多一些步驟就可以解出來了

想法如下

• 如果判斷出有 cycle 的話，將 oneStep 移回 list 的起點，然後 oneStep 和 twoStep 這兩個指標每次都只往前移動一步，再次相遇的那個點就是 cycle 的起點

code  如下
c++

kotlin