C++에서 다단계 연결 리스트 병합(평탄화)하기

문제 소개

이번 문제에서는 다단계(multilevel) 연결 리스트가 주어지며, 이를 하나의 1차원 연결 리스트로 펼치는 평탄화(flatten) 프로그램을 작성해야 합니다.

평탄화는 첫 번째 레벨의 노드들이 연결 리스트 앞쪽에 먼저 배치되고, 그다음 두 번째 레벨의 노드들이 뒤따르는 방식으로 진행됩니다.

다단계 연결 리스트란?

다단계 연결 리스트는 각 노드가 두 개의 링크 포인터를 가지는 다차원 데이터 구조입니다. 하나는 다음 노드를 가리키는 next 포인터이고, 다른 하나는 하나 이상의 노드로 이루어진 자식(child) 리스트를 가리키는 child 포인터입니다. 이 자식 포인터는 다른 리스트 노드를 가리킬 수도 있고, 아무것도 가리키지 않을 수도 있습니다.

입출력 예시

입력:

출력:

1 -> 9 -> 8 -> 4 -> 6 -> 7 -> 3 -> 2 -> 5

해결 접근 방식

가장 간단한 해결 방법은 레벨 순서(level order) 순회와 유사한 알고리즘을 사용하는 것입니다. 첫 번째 노드부터 시작해 같은 레벨에 있는 모든 노드를 차례로 순회하면서, 자식 포인터를 가진 노드를 발견하면 꼬리(tail) 포인터를 이용해 해당 자식 리스트를 현재 연결 리스트의 맨 끝으로 옮깁니다. 이 과정을 모든 자식 노드에 대해 반복하면 리스트가 완전히 평탄화됩니다.

알고리즘 단계

1. 꼬리(tail) 포인터를 첫 번째 레벨의 마지막 노드까지 이동시킵니다.
2. 현재 노드(cur)를 헤드부터 꼬리까지 순회합니다.
3. 현재 노드에 자식 리스트가 존재하면, 자식 리스트를 꼬리 뒤에 연결하고 꼬리를 자식 리스트의 마지막 노드로 갱신합니다.
4. 모든 노드를 순회할 때까지 위 과정을 반복합니다.

C++ 구현 예제

아래 프로그램은 위에서 설명한 로직이 실제로 동작하는 과정을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;

#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))

class Node{
    public:
    int data;
    Node *next;
    Node *child;
};
Node *createList(int *arr, int n){
    Node *head = NULL;
    Node *p;
    int i;
    for (i = 0; i < n; ++i){
        if (head == NULL)
            head = p = new Node();
        else{
            p->next = new Node();
            p = p->next;
        }
        p->data = arr[i];
        p->next = p->child = NULL;
    }
    return head;
}
Node *createList(void){
    int arr1[] = {1, 9, 8, 4, 6};
    int arr2[] = {7, 3, 2};
    int arr3[] = {5};
    Node *head1 = createList(arr1, (sizeof(arr1)/sizeof(arr1[0])));
    Node *head2 = createList(arr2, (sizeof(arr2)/sizeof(arr2[0])));
    Node *head3 = createList(arr3, (sizeof(arr3)/sizeof(arr3[0])));
    head1->child = head2;
    head1->next->child = head3;
    return head1;
}
void flattenLinkedList(Node *head){
    if (head == NULL)
        return;
    Node *tmp;
    Node *tail = head;
    while (tail->next != NULL)
        tail = tail->next;
    Node *cur = head;
    while (cur != tail){
        if (cur->child){
            tail->next = cur->child;
            tmp = cur->child;
            while (tmp->next)
                tmp = tmp->next;
            tail = tmp;
        }
        cur = cur->next;
    }
}
int main(void){
    Node *head = NULL;
    head = createList();
    flattenLinkedList(head);
    cout<<"The flattened Linked List is ";
    while (head != NULL){
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

실행 결과

The flattened Linked List is 1 9 8 4 6 7 3 2 5

복잡도 분석

시간 복잡도: O(N) — 모든 노드를 정확히 한 번씩 방문합니다. 여기서 N은 전체 노드의 개수입니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 기존 포인터만 조작하므로 상수 크기의 추가 메모리만 사용합니다.