Online Judge►LeetCode

[LeetCode] 142 - Linked List Cycle II

題意

在沒有額外空間且不修改的情況下判斷 Linked List 是否有環，並且回傳該環的起點。

解法

先同第一題一樣先使用兩個指標，一個一次一步，另一個則一次兩步直到會合。

假設
從 Linked List 的起點到環的起點為 A
從 環的起點到相遇處為 B
從 相遇處到環的起點為 C

則可以得出下列式子

1
2
3
2(A + B + n(B+C)) = A + B + m(B+C) , 其中 n, m 個別代表慢指針及快指針所繞的圈數
=> 2A + 2B + 2n(B+C) = A + B + m(B+C)
=> A + B = (B+C)(m-2n)

當題目生成時 A, B+C 已經固定，找尋是否有存在 n, m, B 使等式成立

1
2
3
n = 0 時， m = A, 而 B = A(B+C) - A
=> A + A(B+C) - A = A(B+C)  
=> A(B+C) = A(B+C)

因此

1
2
3
4
A + B = (B+C)(m-2n)
=> A + B + C = (B+C)(m-2n) + C
=> A = (B+C)(m-2n-1) + C 
=> A = (B+C)(A-1) + C

因此從 Linked List 起點開始的指針必定會和從相會處開始的指針交於環的起點。

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  if ( head === null ) return null;
  
  let fast = head;
  let slow = head;
  while ( fast.next && fast.next.next ){
    fast = fast.next.next;
    slow = slow.next;
    if ( fast === slow ){
      slow = head;
      while ( slow !== fast ){
        slow = slow.next;
        fast = fast.next;
      }
      return slow;
    }
  }
  return null;
};