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