在C ++中的排序双链表中查找与给定产品的对
概念
对于给定的正唯一元素的双链表，我们的任务是确定双链表中对的乘积等于给定值x的对，而不消耗任何额外空间。
输入项
List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9 x = 8
输出结果
(1, 8), (2, 4)
输入项
List1 = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 x = 6
输出结果
(1, 4), (2,3)
方法
根据针对此问题的简单方法，我们遍历实现两个嵌套循环的链表，并确定所有对，并验证乘积等于x的对。在这里，此问题的时间复杂度将为O（n^2），其中n是双向链表中节点的总数。
讨论了此问题的有效解决方案。这是算法的步骤-
我们初始化两个指针变量，以确定排序的双链表中的候选元素。
我们以双向链表的开头（即first1=head）初始化first1，并以双向链表的最后一个节点（seconds1=last_node）初始化second1。
现在，我们将第一个和第二个指针初始化为第一个和最后一个节点。在这种情况下，我们没有随机访问权限，因此要确定第二个指针，我们访问列表以初始化second1。
已经看到，如果first1和second1的当前和小于x，则我们将first1向前移动。否则，如果first1和second1的当前和大于x，那么我们将back1向后移动。
最后，循环终止条件也不同于阵列。在这种情况下，当两个指针中的任何一个变为NULL或它们彼此交叉（second1->next=first1）或变为相同（first1==second1）时，循环结束。
示例
// C++ program to find a pair with
//给定乘以x的乘积x-
//链表
#include <bits/stdc++.h>
using namespace std;
//Shows Doubly链表 Node
struct Node1 {
int data1;
struct Node1 *next1, *prev1;
};
//显示函数以确定其产品的对
//等于给定值x-
void pairProduct(struct Node1* head1, int x1){
//现在设置两个指针，
//首先是DLL的开头，然后是DLL的结尾。
struct Node1* first1 = head1;
struct Node1* second1 = head1;
while (second1->next1 != NULL)
second1 = second1->next1;
//用于跟踪我们是否找到一对
bool found1 = false;
//现在，当两个指针之一
// become NULL, or they cross each other (second1->next1
//==first1），或者它们变得相同（first1==second1）
while (first1 != NULL && second1 != NULL && first1 != second1 && second1->next1 != first1) {
//找到对
if ((first1->data1 * second1->data1) == x1) {
found1 = true;
cout << "(" << first1->data1 << ", " << second1->data1 << ")" << endl;
//用于先向前移动
first1 = first1->next1;
//用于向后移动第二个
second1 = second1->prev1;
} else {
if ((first1->data1 * second1->data1) < x1)
first1 = first1->next1;
else
second1 = second1->prev1;
}
}
//现在，如果不存在配对
if (found1 == false)
cout << "No找到对";
}
//处插入新节点
// beginning of doubly链表
void insert(struct Node1** head1, int data1){
struct Node1* temp1 = new Node1;
temp1->data1 = data1;
temp1->next1 = temp1->prev1 = NULL;
if (!(*head1))
(*head1) = temp1;
else {
temp1->next1 = *head1;
(*head1)->prev1 = temp1;
(*head1) = temp1;
}
}
//驱动程式码
int main(){
// Create Doubly链表 struct Node1* head1 = NULL;
/*insert(&head1, 9);
insert(&head1, 8);
insert(&head1, 6);
insert(&head1, 5);
insert(&head1, 4);
insert(&head1, 2);
insert(&head1, 1);
int x1 = 8; */
insert(&head1, 7);
insert(&head1, 6);
insert(&head1, 5);
insert(&head1, 4);
insert(&head1, 3);
insert(&head1, 2);
insert(&head1, 1);
int x1 = 6;
pairProduct(head1, x1);
return 0;
}输出结果
(1, 6) (2, 3)