C++で連結リストのループ（循環部分）の長さを求める方法

この記事では、ループ（循環）を含む可能性がある連結リストが与えられたときに、そのループの長さ（ループ内のノード数）を求める方法を解説します。

問題の概要

与えられた連結リストにループが存在する場合は、ループを構成するノードの数を数えて返します。ループが存在しない場合は -1 を返します。

具体例を見てみましょう。

• 入力： 連結リスト：1 → 2 → 3 → 4 → 5 → 6 → 7 → 2（ノード2に戻る）
• 出力： 6

この例では、ノード7の次がノード2に接続されており、ノード2からノード7までの6個のノードがループを形成しています。

解決アプローチ：フロイドの循環検出法

まず、連結リストにループが存在するかどうかを判定する必要があります。これにはフロイドの循環検出アルゴリズム（Floyd's Cycle Finding Algorithm）、いわゆる「ウサギとカメ」の手法が有効です。

アルゴリズムの手順

1. slowPtr（遅いポインタ）は1つずつ、fastPtr（速いポインタ）は2つずつノードを進めます。
2. 両方のポインタが同じノードで出会えば、リストにはループが存在します。fastPtrがNULLに到達すれば、ループはありません。
3. ループが存在する場合、出会った地点から再びポインタを1つずつ進めていき、同じ地点に戻ってくるまでのステップ数を数えます。この数がループの長さになります。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

// 出会った地点からループのノード数を数える関数
int countLoopNodespoint(struct Node *n) {
    int res = 1;
    struct Node *temp = n;
    while (temp->next != n) {
        res++;
        temp = temp->next;
    }
    return res;
}

// フロイドの循環検出法でループを判定し、長さを返す関数
int countLoopNode(struct Node *list) {
    struct Node *slowPtr = list, *fastPtr = list;
    while (slowPtr && fastPtr && fastPtr->next) {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;

        if (slowPtr == fastPtr)
            return countLoopNodespoint(slowPtr);
    }
    return 0;
}

// 新しいノードを作成する補助関数
struct Node *newNode(int key) {
    struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = key;
    temp->next = NULL;
    return temp;
}

int main() {
    // 連結リストの構築：1→2→3→4→5→6→7
    struct Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next->next = newNode(7);

    // ノード7の次をノード2につなげてループを作成
    head->next->next->next->next->next->next->next = head->next;

    cout<<"ループ内のノード数は "<<countLoopNode(head);

    return 0;
}

実行結果

ループ内のノード数は 6

計算量について

• 時間計算量： O(n) — リストを高々一度走査するため、ノード数に対して線形時間で処理できます。
• 空間計算量： O(1) — ポインタ2つ分の追加メモリのみで済みます。

このように、フロイドの循環検出法を使えば、追加のメモリをほとんど使わずに効率的にループの有無を判定し、その長さを求めることができます。