23. Merge k Sorted Lists

[zeikar]

Problem link

https://leetcode.com/problems/merge-k-sorted-lists/

Problem Summary

k개의 정렬된 리스트를 하나의 정렬된 리스트로 머지하는 문제.

Solution

간단한 해결책으로는 모든 리스트를 하나로 붙인 다음 정렬하는 것이다. 시간 복잡도는 O(N logN)이고 충분히 빨리 동작한다.

풀이를 보니 분할 정복 풀이가 정석인 것 같아서 분할 정복 스타일로 다시 풀었는데 이게 시간, 공간이 더 크다는??
재귀 방식으로 풀었고 가운데를 잘라서 왼쪽 부분 오른쪽 부분을 머지한 결과를 머지하는 방식으로 동작한다. 추가 메모리를 사용하지 않기 위해 left 에다 머지한 결과를 덮어 씌우는 식으로 구현하였다.

더 다양한 풀이는 공식 솔루션 참고.
https://leetcode.com/problems/merge-k-sorted-lists/solution/

Source Code

from typing import Optional, 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]:
        self.mergeTwoLists(lists, 0, len(lists) - 1)
        if len(lists) == 0:
            return None
        return lists[0]

    def mergeTwoLists(self, lists: List[Optional[ListNode]], left: int, right: int) -> None:
        if left >= right:
            return None

        mid = (left + right) // 2
        self.mergeTwoLists(lists, left, mid)
        self.mergeTwoLists(lists, mid + 1, right)

        self.merge(lists, left, mid + 1)
        return None

    def merge(self, lists: List[Optional[ListNode]], left: int, right: int) -> None:
        left_cur = lists[left]
        right_cur = lists[right]
        head = ListNode()
        cur = head

        while left_cur and right_cur:
            if left_cur.val < right_cur.val:
                cur.next = left_cur
                left_cur = left_cur.next
            else:
                cur.next = right_cur
                right_cur = right_cur.next

            cur = cur.next

        if left_cur:
            cur.next = left_cur

        if right_cur:
            cur.next = right_cur

        lists[left] = head.next