Giả sử chúng ta có một danh sách được liên kết đơn lẻ và một giá trị x; chúng ta phải tìm một cặp có tổng bằng x. Chúng tôi phải lưu ý rằng chúng tôi không thể sử dụng thêm bất kỳ không gian nào và độ phức tạp về thời gian dự kiến sẽ là O (n).
Vì vậy, nếu đầu vào là 4 → 7 → 8 → 9 → 10 → 11 → 12, x =19, thì đầu ra sẽ là [(7, 12), (8, 11), (9, 10)]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm convert_to_xor (), điều này sẽ bắt đầu,
-
trước:=NULL
-
trong khi bắt đầu là NULL, do -
-
next_list_node:=next of start
-
tiếp theo của bắt đầu:=XOR địa chỉ của next_list_node và trước đó
-
trước:=bắt đầu
-
start:=next_list_node
-
-
Từ phương thức chính, thực hiện như sau -
-
đầu tiên:=bắt đầu
-
next_list_node:=NULL, trước:=NULL, thứ hai:=bắt đầu
-
trong khi phần tiếp theo của giây không bằng phần trước, hãy làm -
-
tạm thời:=giây
-
thứ hai:=XOR của địa chỉ của (tiếp theo của giây, trước)
-
trước:=tạm thời
-
-
next_list_node:=NULL
-
trước:=NULL
-
cờ:=false
-
trong khi (đầu tiên không bằng NULL và thứ hai không bằng NULL và đầu tiên không bằng thứ hai và đầu tiên không bằng next_list_node), làm -
-
nếu dữ liệu của thứ nhất + dữ liệu của thứ hai giống với x, thì -
-
hiển thị dữ liệu cặp của thứ nhất, dữ liệu của thứ hai
-
cờ:=true
-
tạm thời:=đầu tiên
-
first:=XOR của địa chỉ của (tiếp theo của đầu tiên, trước)
-
trước:=tạm thời
-
tạm thời:=giây
-
thứ hai:=XOR địa chỉ của giây tiếp theo, next_list_node)
-
next_list_node:=temp
-
-
Nếu không
-
nếu dữ liệu của thứ nhất + dữ liệu của thứ hai
-
tạm thời:=đầu tiên
-
first:=XOR của địa chỉ của (tiếp theo của đầu tiên, trước)
-
trước:=tạm thời
-
-
Nếu không
-
tạm thời:=giây
-
second:=XOR địa chỉ của (next of second, next_list_node)
-
next_list_node:=temp
-
-
-
-
nếu cờ giống với false, thì -
-
không có cặp nào
-
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
{4,7,8,9,10,11,12} Đầu ra
(7,12) (8,11) (9,10)