C++で連結リストが循環リンクリストかどうかを判定する方法

この記事では、連結リスト（リンクリスト）が循環リンクリストであるかどうかを判定する方法を解説します。

循環リンクリストの判定アルゴリズム

連結リストが循環しているかどうかを確認するには、以下の手順を実行します。

1. 先頭ノード（ヘッダーノード）へのポインタを別の変数に保存しておきます。
2. リストを順番に走査していきます。
3. 走査中に、あるノードのnextがNULLになった場合はリストの終端に到達したことを意味するため、循環リンクリストではありません。
4. 逆に、走査中のノードが最初に保存しておいた先頭ノードと一致した場合は、リストが一周して元の位置に戻ったことを意味するため、循環リンクリストです。

C++での実装例

#include <iostream>
using namespace std;
class Node{
    public:
    int data;
    Node *next;
};
Node* getNode(int data){
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
bool isCircularList(Node *start){
    if(start == NULL)
        return true;
    Node *node = start->next;
    while(node != NULL && node != start){
        node = node->next;
    }
    if(node == start)
        return true;
    return false;
}
int main() {
    Node *start = getNode(10);
    start->next = getNode(20);
    start->next->next = getNode(30);
    start->next->next->next = getNode(40);
    start->next->next->next->next = getNode(50);
    start->next->next->next->next->next = start;
    if (isCircularList(start))
        cout << "The list is circular list";
    else
        cout << "The list is not circular list";
}

コードの解説

isCircularList関数では、まずリストが空（NULL）の場合にtrueを返します。次に、start->nextから走査を開始し、ノードがNULLになるか、先頭ノードに戻るまでループを繰り返します。ループ終了時にノードが先頭ノードと一致していれば循環リンクリスト、一致しなければ通常の連結リストと判定できます。このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)であり、非常に効率的です。

出力結果

The list is circular list