이 문제에서는 right와 down, 두 개의 포인터 노드로 구성된 연결 리스트가 주어집니다.
Right 노드 : 메인 연결 리스트를 가리키는 포인터입니다.
Down 노드 : 해당 노드에서 시작하는 하위(보조) 연결 리스트를 가리키는 포인터입니다.
모든 연결 리스트는 이미 정렬되어 있는 상태입니다.
우리가 해야 할 작업은 이러한 다층 구조의 연결 리스트를 하나로 펼치는(flat하게 만드는) 프로그램을 작성하는 것이며, 결과로 얻어지는 리스트 역시 정렬된 상태를 유지해야 합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
출력
1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5
해결 접근 방식
이 문제는 연결 리스트에 대한 병합 정렬(merge sort) 아이디어를 응용하면 효율적으로 해결할 수 있습니다. 핵심은 두 개의 정렬된 리스트를 하나로 합치는 mergeList() 함수를 구현하고, 이를 재귀적으로 호출하면서 메인 리스트를 따라 모든 하위 리스트를 순서대로 병합하는 것입니다. 그러면 전체 노드가 down 포인터를 따라 연결된 단일 정렬 리스트로 평탄화됩니다.
동작 과정을 단계별로 정리하면 다음과 같습니다.
- 메인 리스트의 끝에서부터 재귀적으로 탐색을 시작합니다.
- 각 단계에서 현재 노드와 오른쪽에 있는(이미 평탄화된) 리스트를 병합합니다.
- 병합 결과의 right 포인터를 NULL로 설정하여 down 방향의 단일 리스트만 남기도록 만듭니다.
예제
다음 프로그램은 위 해결 방법이 실제로 어떻게 동작하는지 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node *right, *down;
};
Node* head = NULL;
Node* mergeList(Node* a, Node* b){
if (a == NULL)
return b;
if (b == NULL)
return a;
Node* result;
if (a->data < b->data){
result = a;
result->down = mergeList(a->down, b);
}
else{
result = b;
result->down = mergeList(a, b->down);
}
result->right = NULL;
return result;
}
Node* flattenLinkedList(Node* root){
if (root == NULL || root->right == NULL)
return root;
root->right = flattenLinkedList(root->right);
root = mergeList(root, root->right);
return root;
}
Node* push(Node* head_ref, int data){
Node* new_node = new Node();
new_node->data = data;
new_node->right = NULL;
new_node->down = head_ref;
head_ref = new_node;
return head_ref;
}
int main(){
head = push(head, 7);
head = push(head, 1);
head->right = push(head->right, 11);
head->right = push(head->right, 5);
head->right = push(head->right, 4);
head->right->right = push(head->right->right, 12);
head->right->right = push(head->right->right, 6);
head->right->right->right = push(head->right->right->right, 8);
head->right->right->right->right = push(head->right->right->right->right, 16);
head = flattenLinkedList(head);
cout<<"The Flattened Linked list is : \n";
Node* temp = head;
while (temp != NULL){
cout<<temp->data<<" => ";
temp = temp->down;
}
cout<<"NULL";
return 0;
}
출력
The Flattened Linked list is : 1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL
복잡도 분석
시간 복잡도 : 메인 리스트의 노드 수를 N, 각 하위 리스트의 노드 수를 M이라 하면 O(N × M)입니다. 두 리스트를 병합하는 비용이 각 재귀 단계마다 누적되기 때문입니다.
공간 복잡도 : 재귀 호출에 사용되는 스택 공간을 제외하면 추가적인 저장 공간은 O(1)입니다.