C++로 연결 리스트 삽입 정렬 구현하기

문제 개요

연결 리스트(Linked List)가 주어졌을 때, 이 리스트에 삽입 정렬(Insertion Sort)을 적용하여 오름차순으로 정렬하는 문제입니다. 예를 들어 리스트가 [9, 45, 23, 71, 80, 55]와 같다면, 삽입 정렬을 수행한 결과는 [9, 23, 45, 55, 71, 80]이 됩니다.

알고리즘 접근 방법

삽입 정렬은 각 노드를 하나씩 꺼내서 이미 정렬된 부분 리스트 내의 올바른 위치에 삽입하는 방식으로 동작합니다. 여기서 더미(Dummy) 노드를 활용하면 정렬 결과의 맨 앞(head)에 노드를 삽입해야 하는 특수한 경우를 별도의 조건 분기 없이 깔끔하게 처리할 수 있다는 장점이 있습니다.

전체 해결 과정은 다음과 같습니다.

임의의 값을 가진 더미(dummy) 노드를 새로 생성합니다.
node를 주어진 리스트의 첫 번째 노드로 설정합니다.
node가 null이 아닌 동안 아래 과정을 반복합니다.
- nextNode = node의 다음 노드, dummyHead = dummy의 다음 노드, prevDummyHead = dummy로 초기화합니다.
- 아래 조건이 만족될 때까지 내부 루프를 실행합니다.
  - dummyHead가 존재하지 않거나, dummyHead의 값이 node의 값보다 크면:
    - node의 next를 dummyHead로 지정합니다.
    - prevDummyHead의 next를 node로 지정하여 현재 노드를 올바른 위치에 삽입합니다.
    - 내부 루프를 종료합니다.
  - 조건이 만족되지 않으면 prevDummyHead = dummyHead로 갱신하고, dummyHead를 다음 노드로 한 칸 이동합니다.
- node를 nextNode로 이동하여 다음 노드를 처리합니다.
모든 노드를 처리한 후, dummy의 다음 노드(정렬된 리스트의 헤드)를 반환합니다.

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* insertionSortList(ListNode* a) {
       ListNode* dummy = new ListNode(-1);
       ListNode* node = a;
       ListNode* nextNode;
       ListNode* dummyHead;
       ListNode* prevDummyHead;
       while(node != NULL){
         nextNode = node->next;
         dummyHead = dummy->next;
         prevDummyHead = dummy;
         while(1){
            if(!dummyHead || dummyHead->val > node->val){
               node->next = dummyHead;
               prevDummyHead->next = node;
               break;
            }
            prevDummyHead = dummyHead;
            dummyHead = dummyHead->next;
         }
         node = nextNode;
       }
       return dummy->next;
   }
};
main(){
   vector<int> v = {5,3,2,0,-4,7};
   ListNode *head = make_list(v);
   Solution ob;
   print_list(ob.insertionSortList(head));
}

입력 및 출력 결과

입력

{5,3,2,0,-4,7}

출력

[-4, 0, 2, 3, 5, 7]

음수를 포함한 입력값도 문제없이 정렬되는 것을 확인할 수 있습니다.

복잡도 분석

시간 복잡도: 최악의 경우(역순으로 정렬된 리스트) 각 노드마다 정렬된 부분 리스트 전체를 순회해야 하므로 O(n²)입니다. 이미 정렬된 리스트라면 각 노드가 즉시 삽입 위치를 찾으므로 O(n)으로 동작합니다.
공간 복잡도: 기존 노드들의 포인터만 재배열하며 추가적인 메모리를 사용하지 않으므로 O(1)입니다.