Javaで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で交差しています。