在 C++ 中的双向链表中查找具有给定总和的对

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们得到一个双向链表和一个值和。我们的任务是在双向链表中找到具有给定总和的对。

让我们举个例子来理解这个问题，

输入

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

解决方法

该问题的一个简单解决方案是遍历整个链表并逐个获取元素，并在剩余链表中找到总和为 sum 的元素。这是通过使用嵌套循环来完成的。

程序来说明我们的解决方案的工作，

示例

#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<<"未找到此类对！";
}
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)

另一种更有效的方法是使用链表已排序的事实。为此，我们将使用两个指针，一个开始最初指向链表的头部。而另一端最初指向链表的最后一个节点。

现在，我们将添加 then 以找到 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<<"未找到此类对！";
}
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)

以上是 在 C++ 中的双向链表中查找具有给定总和的对 的全部内容， 来源链接： utcz.com/z/353626.html

回到顶部