C++でソートされた二重リンクリストで特定の製品とのペアを検索します

コンセプト

正の異なる要素の特定のソートされた二重リンクリストに関して、私たちのタスクは、余分なスペースを消費することなく、積が特定の値xに等しい二重リンクリスト内のペアを決定することです。

入力

List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9
x = 8

出力

(1, 8), (2, 4)

入力

List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7
x = 6

出力

(1, 4), (2,3)

メソッド

シンプルなアプローチによると この問題では、2つのネストされたループを実装するリンクリストをトラバースし、すべてのペアを決定し、積がxに等しいペアを確認します。ここで、この問題の時間計算量はO（n ^ 2）になります。ここで、nは二重リンクリスト内のノードの総数です。

効率的なソリューション この問題について説明します。アルゴリズムの手順は次のとおりです-

2つのポインター変数を初期化して、ソートされた二重リンクリスト内の候補要素を決定します。

first1を二重リンクリストの開始であるfirst1=headで初期化し、second1を二重リンクリストの最後のノードであるsecond1=last_nodeで初期化します。

ここで、最初と2番目のポインターを最初と最後のノードとして初期化します。この場合、ランダムアクセスがないため、2番目のポインタを決定するために、リストにアクセスしてsecond1を初期化します。

first1とsecond1の現在の合計がxより小さい場合、first1を順方向に移動することがわかりました。それ以外の場合、first1とsecond1の現在の合計がxより大きい場合、second1を逆方向に移動します。

最後に、ループの終了条件もアレイとは異なります。この場合、2つのポインターのいずれかがNULLになるか、互いに交差するか（second1-> next =first1）、または同じになる（first1 ==second1）と、ループは終了します。

例

// C++ program to find a pair with
// given product x in sorted Doubly
// Linked List
#include <bits/stdc++.h>
using namespace std;
//Shows Doubly Linked List Node
struct Node1 {
   int data1;
   struct Node1 *next1, *prev1;
};
// Shows function to determine pair whose product
// equal to given value x
void pairProduct(struct Node1* head1, int x1){
   // Now set two pointers,
   // first to the beginning of DLL and second to the end of DLL.
   struct Node1* first1 = head1;
   struct Node1* second1 = head1;
   while (second1->next1 != NULL)
      second1 = second1->next1;
   // Used to track if we find a pair or not
   bool found1 = false;
   // Now the loop terminates when either of two pointers
   // become NULL, or they cross each other (second1->next1
   // == first1), or they become same (first1 == second1)
   while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
      // pair found
      if ((first1->data1 * second1->data1) == x1) {
         found1 = true;
         cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
         // Used to move first in forward direction
         first1 = first1->next1;
         // Used to move second in backward direction
         second1 = second1->prev1;
      } else {
         if ((first1->data1 * second1->data1) < x1)
            first1 = first1->next1;
         else
            second1 = second1->prev1;
      }
   }
   // Now if pair is not present
   if (found1 == false)
      cout << "No pair found";
}
// Shows a utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node1** head1, int data1){
   struct Node1* temp1 = new Node1;
   temp1->data1 = data1;
   temp1->next1 = temp1->prev1 = NULL;
   if (!(*head1))
      (*head1) = temp1;
   else {
      temp1->next1 = *head1;
      (*head1)->prev1 = temp1;
      (*head1) = temp1;
   }
}
// Driver Code
int main(){
   // Create Doubly Linked List struct Node1* head1 = NULL;
   /*insert(&head1, 9);
   insert(&head1, 8);
   insert(&head1, 6);
   insert(&head1, 5);
   insert(&head1, 4);
   insert(&head1, 2);
   insert(&head1, 1);
   int x1 = 8; */
   insert(&head1, 7);
   insert(&head1, 6);
   insert(&head1, 5);
   insert(&head1, 4);
   insert(&head1, 3);
   insert(&head1, 2);
   insert(&head1, 1);
   int x1 = 6;
   pairProduct(head1, x1);
   return 0;
}

出力

(1, 6)
(2, 3)