# LeetCode Medium 142. Linked List Cycle II

tags: leetcode

この問題はRustが使えなかったのでC++です．

問題

• Explore
• Problems

アイデア

以前やった問題と同じです．

propyon.hateblo.jp

循環するような点を探す問題ではFloyd's cycleが使えます．

解法

2つのポインタを使います．一方(fast)はもう一方(slow)よりも2倍動きます．

開始地点→ループ開始地点→両者が合う地点→ループ開始地点

これらの間の距離をそれぞれx(開始地点→ループ開始地点)，y(ループ開始地点→両者が会う地点)，z(両者が会う地点→ループ開始地点)とします．

slowとfastはslowがx+y，fastがx+y+z+y=2(x+y)で会います．というのも，fastはslowの2倍動くからです．

fastの式を解くと，x=zとなります．

よって，以下のC++のコードでは最初のループでslowを｢両者が会う地点｣に置きます．次にfastを｢開始地点｣に置き，両者をそれぞれx(開始地点→ループ開始地点)=z(両者が会う地点→ループ開始地点に動かします．

これによって答えを求めることが出来ます．

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
  ListNode *detectCycle(ListNode *head) {
    if (!head || !head->next)
      return NULL;
    
    auto slow = head->next;
    auto fast = head->next->next;
    
    while (slow != fast) {
      if (!fast || !fast->next)
        return NULL;
      slow = slow->next;
      fast = fast->next->next;
    }
    
    fast = head;
    while (slow != fast) {
      slow = slow->next;
      fast = fast->next;
    }
    return slow;
  }
};