数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中双向链表中查找具有给定和的配对
在这个问题中，我们给定一个双向链表和一个值 sum。我们的任务是在双向链表中找到具有给定和的配对。
让我们举个例子来理解这个问题，
输入
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<<"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)
另一种更有效的方法是利用链表已排序的事实。为此，我们将使用两个指针，一个 start 指针最初指向链表的头部。另一个 end 指针最初指向链表的最后一个节点。
现在，我们将它们加起来以找到 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)
更新于: 2021年3月16日
219 次查看
广告