C++の二重リンクリストで指定された合計のペアを検索します

この問題では、二重にリンクされたリストと値の合計が与えられます。私たちのタスクは、二重にリンクされたリストで特定の合計を持つペアを見つけることです。

問題を理解するために例を見てみましょう

入力

head − 2 <-> 5 <-> 6 <-> 9 <-> 12
x = 11

出力

(2, 9), (5, 6)

説明

For pairs (2, 9), the sum of values is 11
For pairs (5, 6), the sum of values is 11

ソリューションアプローチ

この問題の簡単な解決策は、リンクリスト全体をトラバースし、要素を1つずつ取得して、残りのリンクリストで合計が合計である要素を見つけることです。これは、ネストされたループを使用して行われます。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
   struct Node *first = head;
   int pairCount = 0;
   while (first != NULL) {
      struct Node *second = first -> next;
      while(second != NULL){
         if ((first->data + second->data) == sum) {
            pairCount++;
            cout<<"("<<first->data<<",
            "<<second->data<<")\n";
         }
         second = second -> next;
      }
      first = first -> next;
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
   struct Node *temp = new Node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   if (!(*head))
      (*head) = temp;
   else{
      temp->next = *head;
      (*head)->prev = temp;
      (*head) = temp;
   }
}
int main() {
   struct Node *head = NULL;
   insert(&head, 12);
   insert(&head, 9);
   insert(&head, 6);
   insert(&head, 5);
   insert(&head, 2);
   int sum = 11;
   cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
   findSumPairs(head, sum);
   return 0;
}

出力

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)

たまたまより効果的な別のアプローチは、リンクリストがソートされているという事実を使用することです。このために、2つのポインターを使用します。1つは最初にリンクリストの先頭を指し始めます。そして、もう一方の端は最初にリンクリストの最後のノードを指しています。

次に、sumValを見つけるために追加し、それを

given sum.
If sumVal > sum, move end pointer leftwards.
If sumVal < sum, move start pointer rightwards.
If sumVal == sum, print both values, move start pointer rightwards.

ポインタが交差すると、ループから抜け出します。また、見つかったペアの数をカウントします。0に等しい場合は、「そのようなペアは見つかりませんでした！」と出力します。

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
   struct Node *start = head;
   struct Node *end = head;
   while (end->next != NULL)
      end = end->next;
   int pairCount = 0;
   while (start != NULL && end != NULL && start != end &&
   end->next != start) {
      if ((start->data + end->data) == sum) {
         pairCount++;
         cout<<"("<<start->data<<", "<<end->data<<")\n";
         start = start->next;
         end = end->prev;
      }
      else if ((start->data + end->data) < sum)
         start = start->next;
      else
         end = end->prev;
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
   struct Node *temp = new Node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   if (!(*head))
      (*head) = temp;
   else{
      temp->next = *head;
      (*head)->prev = temp;
      (*head) = temp;
   }
}
int main() {
   struct Node *head = NULL;
   insert(&head, 12);
   insert(&head, 9);
   insert(&head, 6);
   insert(&head, 5);
   insert(&head, 2);
   int sum = 11;
   cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
   findSumPairs(head, sum);
   return 0;
}

出力

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)