在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)