循環リンクリストの検出

問題概要

リンクリストの先頭ノードheadが与えられたとき、循環構造の有無を判定する。循環構造とは、ノードのnextポインタを追跡することで再訪問可能なノードが存在する状態を指す。循環が存在しない場合はfalseを返す。

入力例

例1: head = [3,2,0,-4], pos=1 → true
例2: head = [1,2], pos=0 → true
例3: head = [1], pos=-1 → false

解法: フロイドの循環検出法

異なる速度の2つのポインタを使用する。低速ポインタは1ノードずつ、高速ポインタは2ノードずつ進む。循環が存在すれば必ず両ポインタが交差する。

#include <stdbool.h>

bool has_cycle(struct ListNode *head) {
    struct ListNode *tortoise = head;
    struct ListNode *hare = head;
    
    while (hare != NULL && hare->next != NULL) {
        tortoise = tortoise->next;
        hare = hare->next->next;
        
        if (tortoise == hare) {
            return true;
        }
    }
    return false;
}

注意点

高速ポインタのステップ数を3以上にすると、循環サイズによっては検出できないケースが発生する。ステップ数2が最も安定した解法である。

入環ノードの特定

問題概要

循環リンクリストにおいて、循環が開始するノード（入環ノード）を返す。循環が存在しない場合はNULLを返す。

解法の数学的根拠

低速ポインタと高速ポインタの出会い点をM、入環ノードをEとする。先頭からEまでの距離をL、EからMまでの距離をX、循環の長さをCとすると：

2(L + X) = L + X + nC → L = nC - X

この関係を利用し、出会い点と先頭から同速度で進むポインタが再び交差する点が入環ノードとなる。

struct ListNode *find_cycle_entry(struct ListNode *head) {
    struct ListNode *tortoise = head;
    struct ListNode *hare = head;
    
    while (hare != NULL && hare->next != NULL) {
        tortoise = tortoise->next;
        hare = hare->next->next;
        
        if (tortoise == hare) {
            struct ListNode *finder = head;
            while (finder != tortoise) {
                finder = finder->next;
                tortoise = tortoise->next;
            }
            return finder;
        }
    }
    return NULL;
}

動作説明

1. 循環検出で出会い点を特定
2. 先頭ノードと出会い点から同速度でポインタを移動
3. 両ポインタが一致した点が入環ノード