정렬된 단일 연결 리스트(singly linked list)와 목표 값 x가 주어졌을 때, 두 노드의 데이터 합이 x가 되는 모든 쌍(pair)을 찾아야 합니다. 여기서 중요한 제약 조건은 추가 공간을 사용할 수 없다는 점과, 시간 복잡도가 O(n)이어야 한다는 점입니다.
예를 들어 입력이 4→7→8→9→10→11→12이고 x = 19라면, 출력은 다음과 같습니다.
[(7, 12), (8, 11), (9, 10)]
접근 방법
배열이라면 양 끝에 두 개의 포인터를 두고 안쪽으로 이동시키는 '투 포인터' 기법으로 간단히 해결할 수 있습니다. 하지만 단일 연결 리스트는 뒤로 이동할 수 없기 때문에 이 방법을 그대로 적용하기 어렵습니다.
이 문제의 핵심은 XOR 연결 리스트(XOR Linked List) 기법입니다. 각 노드의 next 필드에 이전 노드 주소와 다음 노드 주소의 XOR 값을 저장하면, 하나의 포인터 필드만으로도 앞·뒤 양방향 탐색이 가능해집니다. 이렇게 변환된 리스트에서는 배열처럼 양 끝에서부터 포인터를 이동시키며 쌍을 찾을 수 있습니다.
알고리즘 단계
- convert_to_xor() 함수를 정의합니다.
- prev := NULL로 초기화합니다.
- start가 NULL이 아닐 때까지 반복합니다.
- next_list_node := start의 다음 노드
- start의 next := next_list_node의 주소와 prev의 주소를 XOR한 값
- prev := start
- start := next_list_node
- 메인 로직에서 다음을 수행합니다.
- first := 시작 노드(start)
- next_list_node := NULL, prev := NULL, second := start
- second의 next가 prev와 같지 않을 동안 반복합니다(리스트의 마지막 노드를 찾는 과정).
- temp := second
- second := second의 next 주소와 prev 주소의 XOR 값
- prev := temp
- next_list_node := NULL, prev := NULL, flag := false로 설정합니다.
- first ≠ NULL, second ≠ NULL, first ≠ second, first ≠ next_list_node를 만족하는 동안 반복합니다.
- first의 데이터 + second의 데이터가 x와 같다면
- (first의 데이터, second의 데이터) 쌍을 출력합니다.
- flag := true로 설정합니다.
- first는 앞쪽으로 한 칸, second는 뒤쪽으로 한 칸 이동시킵니다(XOR 디코딩 활용).
- 그렇지 않고 first의 데이터 + second의 데이터가 x보다 작다면 first를 다음 노드로 이동시킵니다.
- 그 외의 경우에는 second를 이전 노드로 이동시킵니다.
- first의 데이터 + second의 데이터가 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)
복잡도 및 참고 사항
리스트를 XOR 형태로 변환하는 데 O(n), 두 포인터가 서로 마주 보며 이동하는 데 최대 O(n)이 소요되므로 전체 시간 복잡도는 O(n)입니다. 또한 기존 노드의 next 필드를 재활용하기 때문에 포인터 변수 몇 개를 제외하면 추가 공간을 사용하지 않습니다. 다만 포인터에 대한 비트 XOR 연산은 컴파일러나 플랫폼에 따라 이식성 문제가 발생할 수 있으므로, 실무보다는 알고리즘 학습이나 코딩 인터뷰 준비 관점에서 이해하는 것이 좋습니다.