C++로 연결 리스트 정렬하기 – O(n log n) 병합 정렬 완벽 가이드

문제 소개

연결 리스트(Linked List)가 주어졌을 때, 이를 O(n log n)의 시간 복잡도와 상수 공간 복잡도 조건 하에서 정렬하는 것이 이 글의 목표입니다. 예를 들어 입력 리스트가 [4, 2, 1, 3]이라면, 정렬 후에는 [1, 2, 3, 4]가 되어야 합니다.

배열과 달리 연결 리스트는 임의 접근(random access)이 불가능하기 때문에 퀵 정렬이나 힙 정렬을 그대로 적용하기 어렵습니다. 따라서 이 문제는 병합 정렬(Merge Sort)을 활용하는 것이 가장 효율적이며, 재귀적으로 리스트를 분할한 뒤 정렬된 순서로 병합하는 방식으로 해결할 수 있습니다.

해결 접근 방법

먼저 두 개의 정렬된 리스트를 하나의 정렬된 리스트로 합치는 merge() 메서드를 정의합니다. 이 메서드는 두 리스트 l1과 l2를 인자로 받습니다.

이후 sortList() 메서드는 다음과 같은 순서로 동작합니다.

종료 조건 확인: head가 NULL이거나 head의 다음 노드가 NULL이면(노드가 0개 또는 1개뿐이면) 이미 정렬된 상태이므로 head를 그대로 반환합니다.
포인터 초기화: slow와 fast를 head로, prev를 NULL로 초기화합니다.
중간 지점 찾기: fast가 NULL이 아니고 fast의 다음 노드도 NULL이 아닌 동안 다음을 반복합니다.
- prev = slow
- slow = slow->next
- fast = fast->next->next
이것은 흔히 '거북이와 토끼' 기법이라고 불리는 방식으로, slow는 한 칸씩, fast는 두 칸씩 이동하여 fast가 끝에 도달할 때 slow는 정확히 리스트의 중간에 위치하게 됩니다.
리스트 분할: prev->next = NULL로 설정하여 리스트를 앞부분(head~prev)과 뒷부분(slow~끝) 두 개로 나눕니다.
재귀 호출: l1 = sortList(head), l2 = sortList(slow)로 각 부분 리스트를 재귀적으로 정렬합니다.
병합 및 반환: 마지막으로 merge(l1, l2)를 호출해 두 정렬된 리스트를 합쳐 반환합니다.

C++ 구현 예제

아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class ListNode{
    public:
    int val;
    ListNode *next;
    ListNode(int data){
        val = data;
        next = NULL;
    }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}
class Solution {
    public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next)return head;
        ListNode *slow = head, *fast = head, *prev = NULL;
        while(fast && fast->next){
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = NULL;
        ListNode* l1 = sortList(head);
        ListNode* l2 = sortList(slow);
        return mergeList(l1,l2);
    }
    ListNode* mergeList(ListNode* l1, ListNode* l2){
        ListNode* temp = new ListNode(0);
        ListNode* p =temp;
        while(l1 && l2){
            if(l1->val<=l2->val){
                p->next = l1;
                l1 = l1->next;
            }else{
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if(l1){
            p->next = l1;
        }
        if(l2){
            p->next = l2;
        }
        return temp->next;
    }
};
main(){
    vector<int> v = {4,2,1,3,5,19,18,6,7};
    ListNode *h1 = make_list(v);
    Solution ob;
    print_list((ob.sortList(h1)));
}

입력

[4, 2, 1, 3, 5, 19, 18, 6, 7]

출력

[1, 2, 3, 4, 5, 6, 7, 18, 19]

동작 원리 요약

mergeList() 함수는 더미(dummy) 노드를 생성한 뒤, 두 리스트의 값을 비교하면서 작은 값부터 차례로 연결합니다. 한쪽 리스트가 먼저 끝나면 남은 노드들을 그대로 뒤에 붙여주는 방식으로, 두 정렬된 리스트를 선형 시간 O(n) 안에 하나로 합칠 수 있습니다.

전체 알고리즘은 매번 리스트를 절반으로 나누어 재귀적으로 정렬하므로 시간 복잡도는 O(n log n)이며, 추가 배열 없이 노드 포인터만 조작하므로 공간 복잡도 측면에서도 효율적입니다. 다만 재귀 호출에 의한 스택 사용이 있으므로, 완전한 상수 공간이 필요하다면 반복문 기반의 bottom-up 병합 정렬로 변형하는 것도 고려해 볼 수 있습니다.