Tìm các cặp có tổng cho trước trong danh sách liên kết kép trong C ++

Trong bài toán này, chúng ta được cung cấp một danh sách được liên kết kép và một tổng giá trị. Nhiệm vụ của chúng ta là tìm các cặp có tổng cho trước trong danh sách được liên kết kép.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

(2, 9), (5, 6)

Giải thích

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là duyệt qua toàn bộ danh sách liên kết và lấy từng phần tử một và tìm phần tử trong danh sách liên kết còn lại có tổng là tổng. Điều này được thực hiện bằng cách sử dụng các vòng lặp lồng nhau.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

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

Một cách tiếp cận khác hiệu quả hơn là sử dụng thực tế là danh sách liên kết được sắp xếp. Đối với điều này, chúng tôi sẽ sử dụng hai con trỏ, một con trỏ bắt đầu trỏ vào đầu danh sách được Liên kết. Và đầu kia ban đầu trỏ vào nút cuối cùng của danh sách được Liên kết.

Bây giờ, chúng ta sẽ thêm sau đó để tìm sumVal và sau đó so sánh nó với

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.

Khi các con trỏ chéo nhau thoát ra khỏi vòng lặp. Ngoài ra, chúng tôi sẽ đếm số cặp được tìm thấy, nếu nó bằng 0, hãy in "Không tìm thấy cặp nào như vậy!"

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

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