단일 연결 목록과 값 x가 있다고 가정합니다. 합이 x와 같은 쌍을 찾아야 합니다. 추가 공간을 사용할 수 없으며 예상 시간 복잡도는 O(n)입니다.
따라서 입력이 4→7→8→9→10→11→12, x =19인 경우 출력은 [(7, 12), (8, 11), (9, 10)]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
convert_to_xor() 함수를 정의하면 시작됩니다.
-
이전 :=NULL
-
시작이 NULL인 동안 수행 -
-
next_list_node :=다음 시작
-
다음 시작 :=next_list_node 및 이전 주소의 XOR
-
이전 :=시작
-
시작 :=next_list_node
-
-
기본 방법에서 다음을 수행하십시오 -
-
첫 번째 :=시작
-
next_list_node :=NULL, 이전 :=NULL, 두 번째 :=시작
-
초의 다음이 이전과 같지 않은 동안 수행 -
-
온도 :=초
-
second :=(next of second, prev)
주소의 XOR -
이전 :=임시
-
-
next_list_node :=NULL
-
이전 :=NULL
-
플래그 :=거짓
-
동안(첫 번째는 NULL과 같지 않고 두 번째는 NULL과 같지 않고 첫 번째는 두 번째와 같지 않고 첫 번째는 next_list_node와 같지 않음), do -
-
첫 번째 데이터 + 두 번째 데이터가 x와 같으면 -
-
첫 번째 쌍 데이터 표시, 두 번째 데이터 표시
-
플래그 :=참
-
임시 :=첫 번째
-
first :=(next of first,prev)
주소의 XOR -
이전 :=임시
-
온도 :=초
-
두 번째 :=다음 두 번째 주소의 XOR, next_list_node)
-
next_list_node :=임시
-
-
그렇지 않으면
-
첫 번째 데이터 + 두 번째 데이터
-
임시 :=첫 번째
-
first :=(next of first,prev)
주소의 XOR -
이전 :=임시
-
-
그렇지 않으면
-
온도 :=초
-
second :=(next of second, next_list_node)
주소의 XOR -
next_list_node :=임시
-
-
-
-
플래그가 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)