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

2023-06-16 12:13:03 81

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

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

输入

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
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<<"("<data<<",
            "<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 = "<输出结果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
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<<"("<data<<", "<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 = "<输出结果Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)

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

输入

解释

解决方法

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

示例

示例

热门推荐

随机推荐