[코테] 리트코드 데크,우선순위 큐 23. Merge k Sorted Lists

23. Merge k Sorted Lists

문제 링크

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

문제 설명

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

제한 사항

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 10^4.

입출력 예 #1

1. Input : lists = [[1,4,5],[1,3,4],[2,6]]
2. Output : [1,1,2,3,4,4,5,6]
3. Explanation The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

입출력 예 #2

1. Input : lists = []
2. Output : []

입출력 예 #3

1. Input : lists = [[]]
2. Output : []

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        root = result = ListNode(None)
        heap = []

        # 각 연결 리스트의 루트를 힙에 저장
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i, lists[i]))

        # 힙 추출 이후 다음 노드는 다시 저장
        while heap:
            node = heapq.heappop(heap)
            idx = node[1]
            result.next = node[2]

            result = result.next
            if result.next:
                heapq.heappush(heap, (result.next.val, idx, result.next))

        return root.next