在C ++中以单链接形式查找给定总和的对，而没有多余空间

假设我们有一个单链表和一个值x；我们必须找到一个总和与x相同的对。我们必须记住，我们不能使用任何额外的空间，并且预期的时间复杂度将为O(n)。

因此，如果输入为4→7→8→9→10→11→12，x = 19，则输出将为[(7,12)，(8,11)，(9,10)]

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数convert_to_xor()，这将开始，

• 上一页：= NULL

• 当start为NULL时，执行-

• next_list_node：=开始的下一个

• 下一个开始：= next_list_node和prev的地址的异或

• 上一个：=开始

• 开始：= next_list_node

• 从主要方法中，执行以下操作-

• 首先：=开始

• next_list_node：= NULL，上一个：= NULL，第二个：=开始

• 虽然下一秒不等于上一个，但是-

• 温度：=秒

• second：=地址的XOR（秒的下一个，上一个）

• 上一页：=临时

• next_list_node：= NULL

• 上一页：= NULL

• 标志：=假

• while（第一个不等于NULL，第二个不等于NULL，第一个不等于second，第一个不等于next_list_node），-

• 如果第一个数据+第二个数据<x，则

• 除此以外

• temp：=首先

• first：=地址的XOR（first，prev的下一个）

• 上一页：=临时

• 温度：=秒

• second：=地址的异或（秒数的下一个，next_list_node）

• next_list_node：=临时

• 显示第一对数据，第二对数据

• 标志：= true

• temp：=首先

• first：=地址的XOR（first，prev的下一个）

• 上一页：=临时

• 温度：=秒

• second：=第二个next，next_list_node的下一个地址的XOR）

• next_list_node：=临时

• 如果第一个数据+第二个数据与x相同，则-

• 除此以外

• 如果flag与false相同，则-

• 没有一对

范例（C ++）

让我们看下面的实现以更好地理解-

#include<bits/stdc++.h>
using namespace std;
class ListNode {
public:
   int data;
   ListNode *next;
   ListNode(int data) {
      this->data = data;
      next = NULL;
   }
};
ListNode *make_list(vector<int> v) {
   ListNode *start = new ListNode(v[0]);
   for (int i = 1; i < v.size(); i++) {
      ListNode *ptr = start;
      while (ptr->next != NULL) {
         ptr = ptr->next;
      }
      ptr->next = new ListNode(v[i]);
   }
   return start;
}
ListNode* XOR (ListNode *a, ListNode *b) {
   return (ListNode*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
void convert_to_xor(ListNode *start) {
   ListNode *next_list_node;
   ListNode *prev = NULL;
   while (start != NULL) {
      next_list_node = start->next;
      start->next = XOR(next_list_node, prev);
      prev = start;
      start = next_list_node;
   }
}
void get_pared_sum(ListNode *start, int x) {
   ListNode *first = start;
   ListNode *next_list_node = NULL, *prev = NULL;
   ListNode *second = start;
   while (second->next != prev) {
      ListNode *temp = second;
      second = XOR(second->next, prev);
      prev = temp;
   }
   next_list_node = NULL;
   prev = NULL;
   bool flag = false;
   while (first != NULL && second != NULL && first != second && first != next_list_node) {
      if ((first->data + second->data)==x) {
         cout << "(" << first->data << ","<< second->data << ")" << endl;
         flag = true;
         ListNode *temp = first;
         first = XOR(first->next,prev);
         prev = temp;
         temp = second;
         second = XOR(second->next, next_list_node);
         next_list_node = temp;
      }
      else{
         if ((first->data + second->data) < x) {
            ListNode *temp = first;
            first = XOR(first->next,prev);
            prev = temp;
         }
         else{
            ListNode *temp = second;
            second = XOR(second->next, next_list_node);
            next_list_node = temp;
         }
      }
   }
   if (flag == false)
      cout << "No pair found" << endl;
}
int main() {
   vector<int> v = {4,7,8,9,10,11,12};
   ListNode* start = make_list(v);
   int x = 19;
   convert_to_xor(start);
   get_pared_sum(start,x);
}

输入值

{4,7,8,9,10,11,12}

输出结果

(7,12) (8,11) (9,10)