假设我们有一个单链表和一个值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相同,则-
没有一对
让我们看下面的实现以更好地理解-
#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)