두 정렬된 연결 리스트 병합 알고리즘 구현

이미 정렬된 두 개의 연결 리스트를 하나의 정렬된 리스트로 병합하는 문제는 자료구조와 알고리즘의 기초를 다지는 데 매우 중요합니다. 이 문제는 주로 재귀(Recursion) 방식과 반복문(Iteration) 방식을 사용하여 해결할 수 있습니다.

1. 재귀 알고리즘을 이용한 병합

재귀 방식은 문제를 더 작은 단위로 쪼개어 해결하는 접근법입니다. 두 리스트의 현재 노드 값을 비교하여 더 작은 값을 가진 노드를 선택하고, 해당 노드의 다음 포인터에 나머지 노드들을 병합한 결과를 연결하는 방식입니다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* headA, ListNode* headB) {
        // 한쪽 리스트가 비어있으면 다른 쪽 리스트를 반환
        if (headA == nullptr) return headB;
        if (headB == nullptr) return headA;

        // 현재 노드 중 값이 작은 쪽을 선택하여 재귀 호출 진행
        if (headA->val <= headB->val) {
            headA->next = mergeTwoLists(headA->next, headB);
            return headA;
        } else {
            headB->next = mergeTwoLists(headA, headB->next);
            return headB;
        }
    }
};

재귀 방식의 핵심은 현재 단계에서 가장 작은 노드를 확정 짓고, 그 뒤에 붙을 '나머지 정렬된 리스트'는 하위 재귀 함수가 알아서 처리해 줄 것이라고 믿는 것입니다. 기저 조건(Base Case)인 리스트의 끝에 도달할 때까지 이 과정이 반복됩니다.

2. 반복문과 더미 노드를 이용한 병합

반복문을 사용하는 방식은 별도의 스택 메모리를 사용하지 않으므로 공간 효율성 측면에서 유리할 수 있습니다. Dummy Node를 생성하여 결과 리스트의 시작점으로 삼고, 두 리스트를 순회하며 작은 값부터 차례대로 연결합니다.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* node1, ListNode* node2) {
        // 결과 리스트를 구성할 더미 노드와 추적 포인터
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (node1 != nullptr && node2 != nullptr) {
            if (node1->val <= node2->val) {
                tail->next = node1;
                node1 = node1->next;
            } else {
                tail->next = node2;
                node2 = node2->next;
            }
            tail = tail->next;
        }

        // 루프가 끝난 후 남아있는 노드들을 연결
        tail->next = (node1 != nullptr) ? node1 : node2;

        return dummy.next;
    }
};

반복문 방식에서는 두 리스트 중 하나가 먼저 끝날 때까지 비교를 계속합니다. 루프가 종료된 시점에 아직 순회가 끝나지 않은 리스트가 있다면, 해당 리스트의 나머지 부분은 이미 정렬된 상태이므로 단순히 결과 리스트의 끝에 붙여주기만 하면 됩니다.

이와 같이 연결 리스트 병합은 포인터의 조작과 조건부 로직을 연습하기에 매우 좋은 예제이며, 시간 복잡도는 두 리스트의 총 노드 수에 비례하는 O(n + m)을 가집니다.

태그: C++ LinkedList algorithm recursion iteration

11월 4일 01:40에 게시됨