Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q27

Q27 Merge k Sorted Lists

Q

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.

Sample Input

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

Input: lists = []
Output: []

Input: lists = [[ ]]
Output: []

Constraints

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won’t exceed 104.

1. My Solution <- Given Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Node():
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next

class Solution():
    def mergeKLists(self, lists: List[Node]) -> Node:
        root = result = Node(None) #save result's address at root
        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

Input list, lists = [[1,2,4], [3,4,5], [2,4,7]] is given as LINKED-LIST. It is like [node(val=1, points 2), node(val=3, points 4), node(val=3, points 4)]. Don’t be confused by the input.

By the way, let’s continue with the example above. len = 3, so i = 0, 1, 2. See the case when i = 0. lists[0] is node(val = 1, points 2), so it is the address. Namely this is not zero, then executes if. Push the tuple (val, idx, node address) to the heap(list). Repeat k(length of the array) times.

Loop until heap array is empty. Node that poped out first is the MINIMUM NODE that has the smallest value(*because tuple’s first element is the value of the node, so searching is done depend on the value size). heapq.heappop() is method of the proirity Queue, that pops the minimum value out. As a result node is assigned the tuple, (min value, idx when in lists, address of min node). Then let result points the min node.

Push result node to the next node(=min node). Check if next node exists. If it does, push the same tuple set of the next node, (value of result.next node, idx, address of result.next node). Then go to the top and repeat the loop.

*보충 설명 : 처음에 for loop에서 lists에 있는 모든 원소들(즉 모든 linked-list의 head-node)을 heap list에 tuple 형태로 저장한다. 이때 tuple은 (head-node의 값, list에서 몇 번째 원소인지(idx), head-node 자체의 주소)로 이루어져 있다.

이후 while 루프는 heap list의 모든 원소가 pop out 될 때까지 반복된다. 먼저 node에 heappop을 이용해 현재 heap list에서 가장 작은 value를 가진 node(이하 min node)를 불러오며, idx를 저장하고 result라는 node가 min node를 가르키도록 한다.

result node를 다음 노드로 넘긴다. 그 후 다음 노드가 존재하는지 확인하고, 존재하는 경우 다음 노드에 대해서 tuple set을 만들어 다시 heap list에 넣고 loop를 다시 따라간다. tuple set에서 idx를 기록하는 이유는 원래 linked 되어있던 라인을 그대로 따라가기 위해서이다.

Overall Review

From the first step, managing the input of this question is pretty hard. Input is given as a list of the head nodes, so handling those element properly is the first challenge.

The next step, is not that easy either. In the loop, building the structure that keep appedending the next node(heapq.heappush) and keep comparing by using the method heapq.heappop takes much time to understand. It’s really impressive that pushing head node to the heap list first, then keep heappop smallest node & heappush next node.

Just understanding the given solution, I’m so impressed by the beautiful design of the algorithm.

참고