C++で連結リストの循環を検出する：サイクルの起点ノードを見つける方法

問題の概要

連結リストが与えられ、その中に循環（サイクル）が存在するかどうかを判定することを考えます。循環の位置を表すために、pos という整数値を使用します。pos は、リストの末尾（tail）が接続されているノードの位置を示します。pos が -1 の場合、リストには循環が存在しないことを意味します。

例えば、連結リストが [5, 3, 2, 0, -4, 7] で pos = 1 である場合、循環が存在し、末尾のノードは2番目のノード（値 3 のノード）に接続されていることになります。なお、この問題には「リストそのものを変更してはいけない」という制約があります。

解法のアルゴリズム：フロイドの循環検出法

この問題は、フロイドの循環検出アルゴリズム（ウサギとカメのアルゴリズムとも呼ばれます）を用いて効率的に解くことができます。slow ポインタと fast ポインタを用意し、slow は1ノードずつ、fast は2ノードずつ進めます。循環が存在する場合、2つのポインタは必ずループ内のどこかで出会います。その後、slow を head に戻して両者を同じ速度で進めると、再び出会う位置が循環の起点ノードとなります。

具体的な手順は以下の通りです。

• slow と fast をどちらも head に初期化する
• slow、fast、および fast の次のノードが存在する間、以下を繰り返す
  • slow を1つ先に進める
  • fast を2つ先に進める
  • slow と fast が一致したら、ループを抜ける
• fast が NULL、または fast の次のノードが存在しない場合は、循環が存在しないため NULL を返す
• slow と fast が一致している場合（循環が存在する場合）
  • slow を head に戻す
  • slow と fast が一致するまで、両方を1ノードずつ進める
• slow を返す（これが循環の起点となるノード）

なぜこのアルゴリズムが機能するのか

head から循環の起点までの距離を a、循環の起点から出会い点までの距離を b、出会い点から循環の起点までの距離を c とすると、fast の移動距離は常に slow の2倍であるため、a + b + c + b = 2(a + b) という式が成り立ちます。これを整理すると c = a が導かれ、「出会い点から循環の起点までの距離」と「head から循環の起点までの距離」が等しいことが分かります。そのため、slow を head に戻して両方を1ノードずつ進めると、2つのポインタは必ず循環の起点で再び出会うのです。

それでは、以下の実装例を見て、より深く理解していきましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
        int val;
        ListNode *next;
        ListNode(int data){
            val = data;
            next = NULL;
        }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
ListNode *get_node(ListNode *head, int pos){
    ListNode *ptr = head;
    if(pos != -1){
        int p = 0;
        while(p < pos){
            ptr = ptr->next;
            p++;
        }
        return ptr;
    }
    return NULL;
}
class Solution {
    public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(slow && fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)break;
        }
        if(!fast || !fast->next)return NULL;
        if(slow == fast){
            slow = head;
            while(slow!=fast){
                slow = slow->next;
                fast = fast->next;
            }
        }
        return slow;
    }
};
main(){
    Solution ob;
    vector<int> v = {5,3,2,0,-4,7};
    ListNode *head = make_list(v);
    int pos = 1;
    ListNode *lastNode = get_node(head, v.size() - 1);
    lastNode->next = get_node(head, pos);
    cout << "Tail is connected to the node with value:" <<ob.detectCycle(head)->val;
}

入力

[5,3,2,0,-4,7]
1

出力

Tail is connected to the node with value:3

この出力から、末尾のノードが値 3 のノード（リストの2番目）に接続されていること、つまり循環の起点が値 3 のノードであることが確認できます。