Javaで2つの連結リストの交点を見つける方法

連結リスト（Linked List）は、各ノードが2つのブロックで構成される線形データ構造です。一方のブロックにはノードの値（データ）が格納され、もう一方のブロックには次のノードへのアドレス（ポインタ）が格納されます。

ここでは、2つの連結リストが交差するノードを見つける問題を扱います。2つのリストが共通のノードを持つ場合、その交点となるノードを特定します。交点が存在しない場合は、NULL（または空）を出力として返します。

具体例

入力1：

出力：

2

説明： 与えられた連結リストは値「2」のノードで交差しているため、出力として「2」を返します。

入力2：

出力：

NULL

説明： 共通のノードが存在しないため、この場合はNULLを返します。

この問題を解くためのアプローチ

2つの連結リストには、互いに交差する共通のノードが存在します。交点を見つけるには、両方の連結リストを走査し、同じノードを指す位置を特定します。ある時点で、両リストの次のノードへのポインタが一致するため、そのノードの値を返します。

• データと次のノードへのポインタを持つ2つの連結リストを用意します。
• 関数 commonPoint(listnode*headA, listnode*headB) は、2つの連結リストの先頭ポインタをそれぞれ受け取り、交点となるノードの値を返します。
• 連結リストの長さを求める整数型の関数は、リストの先頭から各リストの長さを返します。
• 両方のリストの先頭へのポインタを作成し、長い方のリストを（最初のリストの長さ − 2番目のリストの長さ）の分だけ先に進めます。
• その後、両リストのポインタが同じノードを指すまで同時に走査します。
• 両方のリストが交差するノードの値を返します。

コード例

public class Solution {
   static listnode headA,
   headB;
   static class listnode {
      int data;
      listnode next;
      listnode(int d) {
         data = d;
         next = null;
      }
   }
   int count(listnode head) {
      int c = 0;
      while (head != null) {
         c++;
         head = head.next;
      }
      return c;
   }
   int commonPoint(listnode headA, listnode headB) {
      listnode p1 = headA;
      listnode p2 = headB;
      int c1 = count(headA);
      int c2 = count(headB);
      if (c1 > c2) {
         for (int i = 0; i < c1 - c2; i++) {
            if (p1 == null) {
               return - 1;
            }
            p1 = p1.next;
         }
      }
      if (c1 < c2) {
         for (int i = 0; i < c2 - c1; i++) {
            if (p2 == null) {
               return - 1;
            }
            p2 = p2.next;
         }
      }
      while (p1 != null &amp;&amp; p2 != null) {
         if (p1.data == p2.data) {
            return p1.data;
         }
         p1 = p1.next;
         p2 = p2.next;
      }
      return - 1;
   }
   public static void main(String[] args) {
      Solution list = new Solution();
      list.headA = new listnode(5);
      list.headA.next = new listnode(4);
      list.headA.next.next = new listnode(9);
      list.headA.next.next.next = new listnode(7);
      list.headA.next.next.next.next = new listnode(1);
      list.headB = new listnode(6);
      list.headB.next = new listnode(7);
      list.headB.next.next = new listnode(1);
      System.out.println(list.commonPoint(headA, headB));
   }
}

上記のコードを実行すると、以下の出力が得られます。

出力

7

説明： 与えられた連結リストは「7」で交差しています。

計算量について

このアルゴリズムでは、2つのリストの長さをそれぞれ m、n とすると、長さのカウントと走査にそれぞれリスト全体を一度ずつ辿るため、時間計算量は O(m + n) となります。また、追加のデータ構造を使用しないため、空間計算量は O(1) です。ポインタの長さ調整というシンプルな工夫により、効率的に交点を検出できるのが特徴です。