JavaでLinkedListの中央要素を1回の走査で取得する方法

本記事では、LinkedListの中央要素をたった1回の反復（走査）で取得する方法について解説します。java.util.LinkedListクラスは双方向連結リスト（doubly-linked list）として動作し、インデックスを指定した操作は、リストの先頭または末尾のうち指定インデックスに近い方から走査が行われます。

ここで紹介する手法は「2ポインタ法（低速ポインタと高速ポインタ）」と呼ばれる定番テクニックです。1つは1ノードずつ進むポインタ、もう1つは2ノードずつ進むポインタを使い、高速ポインタがリスト末尾に到達した時点で、低速ポインタが中央要素を指すという仕組みです。

入力と出力の例

入力：

連結リスト: 100 200 330

出力：

リストの中央要素: 200

アルゴリズム

Step 1 - 処理を開始する
Step 2 - LinkedList型の input_list を宣言し、head、second_node、third_node などのノードオブジェクトを用意する
Step 3 - ノードに値を設定し、各ノードを連結してリストを構築する
Step 4 - ポインタ pointer_1 と pointer_2 を用意する。whileループでリストを走査し、pointer_1.next が null になるまで、pointer_1 を2ノード分、pointer_2 を1ノード分進める
Step 5 - pointer_2 の値を結果として表示する
Step 6 - 処理を終了する

例1：main関数内にすべての処理を記述する場合

以下のコードでは、すべての操作を main 関数の中にまとめて記述しています。

public class LinkedList {
   Node head;
   static class Node {
      int value;
      Node next;
      Node(int d) {
         value = d;
         next = null;
      }
   }
   public static void main(String[] args) {
      LinkedList input_list = new LinkedList();
      input_list.head = new Node(100);
      Node second_node = new Node(200);
      Node third_node = new Node(330);
      input_list.head.next = second_node;
      second_node.next = third_node;
      Node current_node = input_list.head;
      System.out.print("連結リストの内容: " );
      while (current_node != null) {
         System.out.print(current_node.value + " ");
         current_node = current_node.next;
      }
      Node pointer_1 = input_list.head;
      Node pointer_2 = input_list.head;
      while (pointer_1.next != null) {
         pointer_1 = pointer_1.next;
         if(pointer_1.next !=null) {
            pointer_1 = pointer_1.next;
            pointer_2 = pointer_2.next;
         }
      }
      System.out.println("\nリストの中央要素: " + pointer_2.value);
   }
}

出力

連結リストの内容: 100 200 330
リストの中央要素: 200

例2：オブジェクト指向スタイルで関数に分割する場合

次のコードでは、中央要素を取得する処理を独立したメソッド get_middle_item としてカプセル化し、オブジェクト指向プログラミングのスタイルで実装しています。

public class LinkedList {
   Node head;
   static class Node {
      int value;
      Node next;
      Node(int d) {
         value = d;
         next = null;
      }
   }
   static void get_middle_item(LinkedList input_list){
      Node pointer_1 = input_list.head;
      Node pointer_2 = input_list.head;
      while (pointer_1.next != null) {
         pointer_1 = pointer_1.next;
         if(pointer_1.next !=null) {
            pointer_1 = pointer_1.next;
            pointer_2 = pointer_2.next;
         }
      }
      System.out.println("\nリストの中央要素: " + pointer_2.value);
   }
   public static void main(String[] args) {
      LinkedList input_list = new LinkedList();
      input_list.head = new Node(100);
      Node second_node = new Node(200);
      Node third_node = new Node(330);
      input_list.head.next = second_node;
      second_node.next = third_node;
      Node current_node = input_list.head;
      System.out.print("連結リストの内容: " );
      while (current_node != null) {
         System.out.print(current_node.value + " ");
         current_node = current_node.next;
      }
      get_middle_item(input_list);
   }
}

出力

連結リストの内容: 100 200 330
リストの中央要素: 200

まとめ

このように、2つのポインタを使った走査を行うことで、リストの長さを事前に求めなくても、時間計算量 O(n)・空間計算量 O(1) のまま1回の反復で中央要素を効率的に取得できます。要素数が偶数の場合は、後半側の中央要素が返される点にも注意してください。