[ 23 ] [ heap ] Merge k Sorted Lists

문제 설명

---

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

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

Example 1:

Input:

• lists = [[1,4,5],[1,3,4],[2,6]]

Output:

• [1,1,2,3,4,4,5,6]

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

Example 2:

Input:

• lists = []

Output:

• []

Example 3:

Input:

• lists = [[]]

Output:

• []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i]is sorted inascending order.
• The sum oflists[i].lengthwon't exceed10^4.

---

풀이 과정

• 문제는 k개의 linked-list가 주어질때, 모든 linked-list를 통합하여 하나의 리스트로 만듬(오름차순으로)

1. 리스트의 모든 요소들을 최소 히프에 넣는다
   • 히프의 특성에 의해 나중에 히프에서 빼줄때 정렬되어서 나올 예정
2. 히프에서 요소를 하나씩 꺼내서, 연결 그래프의 노드로 만들어준 다음 연결 그래프의 맨 마지막 노드의 링크에 넣어준다.
   • linked list 구성하기 위해 루트는 따로 저장해 두고, 맨 마지막을 가리키는 변수 따로 지정
3. 루트 노드를 리턴해주면 된다.

---

소스 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
import heapq
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        answer = []

        for l in lists:
            temp = l
            while temp != None:
                heapq.heappush(heap, temp.val)
                temp = temp.next

        root = ListNode()
        prev = root

        while heap:
            t = heapq.heappop(heap)
            temp = ListNode(val=t, next=None)
            prev.next = temp
            prev = temp

        root = root.next

        return root