Merge Two Sorted Lists

문제

오름차순으로 정렬된 두 개의 연결 리스트 list1과 list2의 헤드(head)가 주어집니다. 이 두 리스트의 노드들을 엮어서 하나의 정렬된 새로운 연결 리스트로 병합하고, 그 병합된 리스트의 헤드를 반환하는 프로그램을 작성하는 문제입니다.

• 입력: 정렬된 연결 리스트 list1, list2 (각 리스트의 노드 개수는 0개에서 50개 사이)
• 출력: 두 리스트가 병합되어 정렬된 새로운 연결 리스트의 헤드

링크: https://leetcode.com/problems/merge-two-sorted-lists

풀이: 재귀(Recursion)를 활용한 직관적인 노드 연결

반복문(while)과 임시 노드(dummy node)를 사용하여 연결하는 방식도 있지만, 재귀를 사용하면 코드를 훨씬 짧고 직관적으로 작성할 수 있습니다. 각 재귀 호출 단계에서 더 작은 값을 가진 노드를 선택하고, 그 노드의 다음(next)을 남은 노드들의 병합 결과로 지정하는 방식입니다.

• 기저 조건 (Base Case):
  • 두 리스트를 순회하다가 list1이 비어있는 상태(null)가 되면, 병합할 대상이 list2밖에 남지 않았으므로 남은 list2를 통째로 반환합니다.
  • 반대로 list2가 비어있다면, 남은 list1을 통째로 반환합니다.
• 값 비교 및 재귀 호출 (Recursive Step):
  • 두 노드의 값(val)을 비교하여 더 작은 값을 가진 노드를 현재 단계의 '선택된 노드'로 삼습니다.
  • list1.val <= list2.val인 경우: list1이 선택됩니다. list1의 다음 노드(list1.next)는 'list1의 나머지 부분'과 'list2 전체'를 병합한 결과가 되어야 하므로, mergeTwoLists(list1.next, list2)를 재귀 호출하여 연결합니다. 이후 선택된 list1을 반환합니다.
  • 반대의 경우: list2가 선택됩니다. list2의 다음 노드는 'list1 전체'와 'list2의 나머지 부분'을 병합한 결과가 되어야 하므로, 재귀 호출 후 list2를 반환합니다.

코드

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 1. 기저 조건: 어느 한 쪽 리스트가 끝에 도달하면 남은 리스트를 그대로 반환
        if (list1 == null) {
            return list2;
        } 
        if (list2 == null) {
            return list1;
        }

        // 2. 두 노드의 값을 비교하여 더 작은 노드를 선택하고 재귀적으로 다음 노드를 연결
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

알고리즘 분류

자료 구조 (Data Structures), 연결 리스트 (Linked List), 재귀 (Recursion)