C++での2つのリンクリストの交差

リンクリストは線形データ構造であり、各ノードには2つのブロックがあり、一方のブロックにはノードの値またはデータが含まれ、もう一方のブロックには次のフィールドのアドレスが含まれます。

各ノードにリスト内の他のノードを指すランダムポインタが含まれるようなリンクリストがあると仮定します。タスクは、2つのリンクリストが互いに交差するノードを見つけることです。それらが交差しない場合は、出力としてNULLまたは空を返します。

例

入力-1：

出力：

2

説明： 指定されたリンクリストはノードで値「2」と交差するため、出力として値「2」を返します。

入力-2：

出力：

NULL

説明： 共通点がないため、この場合はNULLを返します。

この問題を解決するためのアプローチ

互いに交差する共通点を持つ2つのリンクリストがあります。交点を見つけるために、リンクされたリストが同じ値を等しく指していることがわかるまで、両方のリンクリストをトラバースします。ある時点で、リンクリストの次のノードへのポインタは同じになります。したがって、そのポイントの値を返します。

• データと次のノードへのポインタを含む2つのリンクリストを取得します。
• 関数commonPoint（listnode * headA、listnode * headB）は、リンクリストの2つのポインターをそれぞれ受け取り、リンクリストの共通点または交点の値を返します。
• リンクリストの長さを見つける整数関数は、リストの先頭から両方のリンクリストの長さを返します。
• 次に、両方のリストの先頭へのポインタを作成し、（最初のリストの長さ– 2番目のリストの長さ）までの長さが長いリストをトラバースします。
• 次に、次のポインタが等しいことがわかるまでリストをトラバースします。
• 両方のリストが交差する特定のノードの値を返します。

例

#include <bits/stdc++.h>
using namespace std;
class listnode {
   public:
      int data;
   listnode * next;
};
// Find the length of the linked list
int count(listnode * head) {
   int count = 0;
   while (head != NULL) {
      count++;
      head = head -> next;
   }
   return count;
}
//Function to get the common point of two linked list
int commonPoint(listnode * headA, listnode * headB) {
   int len1 = count(headA);
   int len2 = count(headB);
   listnode * p1 = headA;
   listnode * p2 = headB;
   if (len1 > len2) {
      for (int i = 0; i < len1 - len2; ++i) {
         p1 = p1 -> next;
      }
   }
   if (len1 < len2) {
      for (int i = 0; i < len2 - len1; ++i) {
         p2 = p2 -> next;
      }
   }
   while (p1 != NULL and p2 != NULL) {
      if (p1 == p2) {
         return p1 -> data;
      }
      p1 = p1 -> next;
      p2 = p2 -> next;
   }
   return -1;
}
int main() {
   listnode * head;
   listnode * headA = new listnode();
   headA -> data = 5;
   listnode * headB = new listnode();
   headB -> data = 4;
   head = new listnode();
   head -> data = 9;
   headB -> next = head;
   head = new listnode();
   head -> data = 2;
   headB -> next -> next = head;
   head = new listnode();
   head -> data = 7;
   headA -> next = head;
   headB -> next -> next -> next = head;
   head = new listnode();
   head -> data = 3;
   headA -> next -> next = head;
   headA -> next -> next -> next = NULL;
   cout << commonPoint(headA, headB) << endl;
}

上記のコードを実行すると、次のように出力が生成されます

出力

7

説明： 指定されたリンクリストは「7」でマージされています。