C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

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


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

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

入力-1:

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

出力:

2

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

入力-2:

C++での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」でマージされています。

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


  1. C++のリンクリストを使用して2つの多項式を追加します。

    この概念をよりよく理解するために、最初に必要なすべての基本的な内容をブラッシュアップしましょう。 リンクリスト リストのノードにオブジェクトとして各要素を格納するデータ構造です。すべてのメモには、2つの部分のデータハンと次のノードへのリンクが含まれています。 多項式 は変数と係数で構成される数式です。たとえば、x ^ 2-4x + 7 多項式リンクリスト 、多項式の係数と指数は、リストのデータノードとして定義されます。 リンクリストとして保存されている2つの多項式を追加します。同じ累乗の変数の係数を追加する必要があります。リンクリストノードには3つのメンバーが含まれ、係数値は次のノー

  2. Javaで2つのリンクリストの交点を見つける

    リンクリストは線形データ構造であり、各ノードには2つのブロックがあり、一方のブロックにはノードの値またはデータが含まれ、もう一方のブロックには次のフィールドのアドレスが含まれます。 各ノードにリスト内の他のノードを指すランダムポインタが含まれるようなリンクリストがあると仮定します。タスクは、2つのリンクリストが互いに交差するノードを見つけることです。それらが交差しない場合は、出力としてNULLまたは空を返します。 例 入力-1: 出力: 2 説明: 指定されたリンクリストはノードで値「2」と交差するため、値「2」を出力として返します。 入力-2: 出