JavaでLinkedListのループ（循環）を検出する方法を徹底解説

本記事では、Javaを使ってLinkedList（連結リスト）内のループ（循環参照）を検出する方法について詳しく解説します。連結リストとは、複数のデータ構造（ノード）をリンクで順につないだデータ構造であり、各ノードにはデータ本体と、次のノードへの参照が格納されています。

通常の連結リストでは末尾のノードがnullを指しますが、ループが存在する場合は、いずれかのノードがすでに通過したノードを再び指すため、リストを辿ると同じ場所に戻り続けることになります。ここでは、ループの有無を判定できる2つの代表的な手法を紹介します。

入力と出力の確認

入力：

プログラムを実行する

期待される出力：

連結リストにループが存在します

アルゴリズム

ステップ1 - 処理を開始する
ステップ2 - 必要な変数を宣言する
ステップ3 - 値を定義する
ステップ4 - 必要なメンバを持つクラスを定義する
ステップ5 - クラスのインスタンスを作成し、ノードを初期化する
ステップ6 - ループの有無を判定するメソッドを定義する
ステップ7 - HashSetを生成し、先頭ノードから順に要素を追加していく
ステップ8 - 反復処理ごとに、ノードを次の要素へ進める
ステップ9 - mainメソッド内でインスタンスを作成し、pushメソッドでリストに要素を追加する
ステップ10 - check_loopメソッドを呼び出し、判定結果に応じたメッセージをコンソールに表示する
ステップ11 - 処理を終了する

例1：HashSetを使ったループ検出（走査方式）

この例では、リストを先頭から走査しながら、訪問済みのノードをHashSetに記録していきます。走査中に「すでにHashSetに存在するノード」に到達した場合、そのノードを2回以上訪れたことになるため、ループが存在すると判断できます。最後まで走査しても重複が見つからなければ、ループは存在しないことになります。

import java.util.*;
public class Demo {
   static Node head;
   static class Node {
      int data;
      Node next;
      Node(int d){
         data = d;
         next = null;
      }
   }
   static public void push(int new_data){
      Node new_node = new Node(new_data);
      new_node.next = head;
      head = new_node;
   }
   static boolean check_loop(Node head){
      HashSet<Node> s = new HashSet<Node>();
      while (head != null) {
         if (s.contains(head))
            return true;
         s.add(head);
         head = head.next;
      }
      return false;
   }
   public static void main(String[] args){
      System.out.println("The required packages have been imported");
      Demo input_list = new Demo();
      input_list.push(45);
      input_list.push(60);
      input_list.push(75);
      input_list.push(90);
      input_list.head.next.next.next.next = input_list.head;
      if (check_loop(head))
         System.out.println("The loop exists in the linked list");
      else
         System.out.println("The loop doesnot exists in the linked list");
      }
   }

出力

The required packages have been imported
The loop exists in the linked list

例2：フロイドの循環検出法（オブジェクト指向スタイル）

この例では、処理をメソッドとしてカプセル化し、オブジェクト指向プログラミングのスタイルで実装しています。採用しているのは「フロイドの循環検出アルゴリズム（ウサギとカメ）」です。1つずつ進む低速ポインタと、2つずつ進む高速ポインタを用意し、リスト内にループがあれば、いずれ2つのポインタは同じノードで出会います。この性質を利用してループを検出します。

public class Demo {
Node head;
static class Node {
int value;
Node next;
Node(int d) {
value = d;
next = null;
}
}
public boolean check_loop() {
Node first_node = head;
Node second_node = head;
while(first_node != null && first_node.next !=null) {
first_node = first_node.next.next;
second_node = second_node.next;
if(first_node == second_node) {
return true;
}
}
return false;
}
public static void main(String[] args) {
Demo input_list = new Demo();
input_list.head = new Node(45);
Node second_node = new Node(60);
Node third_node = new Node(75);
Node fourth_node = new Node(90);
input_list.head.next = second_node;
second_node.next = third_node;
third_node.next = fourth_node;
fourth_node.next = second_node;
System.out.print("The elements of the linked list are: ");
int i = 1;
while (i <= 4) {
System.out.print(input_list.head.value + " ");
input_list.head = input_list.head.next;
i++;
}
boolean loop = input_list.check_loop();
if(loop) {
System.out.println("\nThere is a loop in the linked list.");
}
else {
System.out.println("\nThere is no loop in the linked list.");
}
}
}

出力

The elements of the linked list are: 45 60 75 90 
There is a loop in the linked list.

2つの手法の比較

HashSetを使う方法は直感的で実装も簡単ですが、訪問済みノードをすべて保持する必要があるため、追加のメモリ領域としてO(n)の空間計算量がかかります。一方、フロイドの循環検出法は追加メモリをほとんど使わず、空間計算量O(1)で実現できる点が大きな利点です。どちらの手法も時間計算量はO(n)ですが、実務ではメモリ効率を重視してフロイドの手法が選ばれることが多くなっています。用途や制約に応じて、適切な方法を選択しましょう。