23. Merge k Sorted Lists

리스트를 오름차순으로 정렬하는 문제

다만 리스트 안에 관계가 linked-list로 이루어져있다. 

 

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

아이디어

1) 기존 linked-list에서 새로운 linked-list를 만드는 방법

   어차피 linked-list의 순서가 의미가 없으므로, value만 가져와 정렬후, 정렬된 값으로 새로 Link-list를 만든다. 

 

* 2차원 배열인줄 알고 for문 두번 돌려서 할려고 했는데, leetcode site에서 출력을 해보니 2차원 배열이 아니더라 

* leetcode에서 출력해본 값

[ListNode{val: 1, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}},
ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}},
ListNode{val: 2, next: ListNode{val: 6, next: None}}]

배열 하나에 3개의 ListNode 구조였다.

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        head = point = ListNode(0)
        node = []
        
        print(lists)
        for item in lists:
            # 2차원 배열에서 하나씩 가져와서 [0]번의 ListNode부터 끝번까지 돌면서 val만 저장
            #2차원 배열인줄 알고 이렇게 했는데
            #while it:
            #    node.append(it.val)
            #    it = it.next
        	while item:
            	node.append(item.val)
                node = node.next
        for x in sorted(node):
            point.next = ListNode(x)
            point = point.next
        
        # head의 처음에는 0이 저장되어 있으므로, 그 다음것부터 보내도록 변경
        return head.next
        

 

2) 우선순위 큐를 이용하는 방법 
문제를 풀고나서 정답을 봤는데, 우선순위 큐를 이용해서 푸는 방법이 있었다. 

우선순위 큐는 이진트리 기반으로 min heap으로 항상 작은 값이 앞에 온다

추가, 삭제시에도 정렬은 항상 유지된다. 

 

각 ListNode의 첫번째 값으로 heap을 만들고, 하나 꺼내고, 나머지 부분을 다시 넣고

sort는 따로 해줄 필요가 없다. heap이니까 알아서 된다. 

# ListNode의 첫번째 값의 val와 idx값으로 heap을 만들자
h = [(l.val, idx) for idx, l in enumerate(result) if l]
heapq.heapify(h)

head = cur = ListNode(None)

while h:
	# 하나 꺼내와서 
    val, idx = heapq.heappop(h)
    # 새로운 ListNode를 만들고
    cur.next = ListNode(val)
    cur = cur.next
    # 꺼내온 후에 이동 시키자
    node = result[idx] = result[idx].next
    
    # 이동한 다음에 node가 남아 있다면 다시 heap에 넣어주자
    if node:
        heapq.heappush(h, (node.val, idx))

return head.next