[파이썬 알고리즘] 10장 - k개 정렬 리스트 병합

 

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

Merge k Sorted Lists - LeetCode

<문제>

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.

 

<예시>

Input: lists = [[1,4,5],[1,3,4],[2,6]]

Output: [1,1,2,3,4,4,5,6]

 

---

 

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

        for i in range(len(lists)):
            if lists[i]:
                # linked list의 root를 heap에 저장
                heapq.heappush(heap, (lists[i].val, i, lists[i]))

        while heap:
            # root가 가장 작은 값을 가진 linked list부터 나온다
            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))

 

다음과 같은 linked list 2개가 있다고 가정하자.

 

 

value가 작은 1 node가 pop된다.

그리고 그 linked list의 다음 노드가 heapq로 insert된다.

 

 

1, 4 중 1이 더 우선순위가 높으므로 1 node가 리턴된다.

그 다음에 다음 node인 3이 heapq로 insert

 

 

 

3, 4 중 3의 우선순위 높으므로 3 node가 리턴

그 다음에 다음 node인 4가 heapq로 insert

 

 

이러한 과정을 반복하다보면 다음과 같은 linked list 생성된다