Sorting(merge sort): 23. Merge k Sorted Lists ★★★

23. Merge k Sorted Lists

 

https://youtu.be/q5a5OiGbT6Q?si=Oe5XE1QtO56CiD-s

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 입력으로 주어진 리스트가 비어 있거나, 리스트의 길이가 0일 경우 None 반환
        if not lists or len(lists) == 0:
            return None

        # 리스트를 병합하여 하나의 리스트가 남을 때까지 반복
        while len(lists) > 1:
            mergedOneList = []  # 병합된 리스트를 저장할 임시 리스트

            # 두 개씩 병합하여 새로운 리스트 생성
            for i in range(0, len(lists), 2):
                l1 = lists[i]  # 첫 번째 리스트
                l2 = lists[i+1] if (i+1) < len(lists) else None  # 두 번째 리스트 (없을 수도 있음)
                # 병합된 결과를 임시 리스트에 추가
                mergedOneList.append(self.mergeList(l1, l2))
            
            # 병합된 리스트를 다시 `lists`에 할당
            lists = mergedOneList

        # 최종적으로 병합된 하나의 리스트 반환
        return lists[0]

    def mergeList(self, l1, l2):
        # 두 정렬된 리스트를 병합하는 함수
        dummy = ListNode()  # 결과 리스트의 시작을 위한 더미 노드 생성
        tail = dummy  # 결과 리스트의 현재 끝 부분을 가리킬 포인터

        # 두 리스트를 비교하면서 병합
        while l1 and l2:
            if l1.val < l2.val:  # l1의 값이 더 작은 경우
                tail.next = l1  # l1의 현재 노드를 결과 리스트에 추가
                l1 = l1.next  # l1의 다음 노드로 이동
            else:  # l2의 값이 더 작거나 같은 경우
                tail.next = l2  # l2의 현재 노드를 결과 리스트에 추가
                l2 = l2.next  # l2의 다음 노드로 이동
            tail = tail.next  # 결과 리스트의 마지막 노드를 갱신
        
        # l1 또는 l2에 남아 있는 노드들을 결과 리스트에 연결
        if l1:
            tail.next = l1
        if l2:
            tail.next = l2

        # 더미 노드의 다음 노드가 병합된 리스트의 시작점
        return dummy.next

 

주석 설명

1. mergeKLists 함수:
   • 주어진 lists를 반복적으로 병합하여 하나의 정렬된 리스트로 만듭니다.
   • 입력 리스트가 비어 있거나, 길이가 0이면 None을 반환합니다.
   • 두 개씩 병합하여 리스트의 크기를 점진적으로 줄입니다.
2. mergeList 함수:
   • 두 개의 정렬된 리스트를 병합합니다.
   • 더미 노드(dummy)를 사용하여 병합된 결과 리스트를 쉽게 연결합니다.
   • 두 리스트 중 하나가 끝날 때까지 노드를 비교하며 병합합니다.
   • 남아 있는 노드들은 그대로 결과 리스트에 연결합니다.

코드 흐름

1. 입력 리스트가 비어 있거나 길이가 0이면 바로 None을 반환합니다.
2. 두 개씩 리스트를 병합하면서 리스트의 길이를 줄여나갑니다.
3. 병합된 결과가 하나의 정렬된 리스트가 되면 반환합니다.

---

시간 복잡도

• mergeKLists 함수는 병합 과정에서 O(log⁡k) 단계가 필요합니다. (k는 초기 리스트의 개수)
• 각 단계에서 두 리스트를 병합하는 데 최대 O(n) 시간이 걸립니다. (n은 리스트의 평균 길이)
• 전체 시간 복잡도는 O(n⋅log⁡k)입니다.

---

장점

• 효율적: 병합 과정을 반복적으로 수행하여 정렬된 리스트를 생성합니다.
• 유지보수성: mergeList 함수로 두 리스트 병합을 분리하여 코드가 간결합니다.

 

https://youtu.be/4FioNNCsQh8?si=Anlz9DWvLtcyiulH

 

추가 문제

264. Ugly Number II : https://leetcode.com/problems/ugly-number-ii/description/

2411. Smallest Subarrays With Maximum Bitwise OR : https://leetcode.com/problems/smallest-subarrays-with-maximum-bitwise-or/description/