###### tags: `Leetcode` `hard` `heap` `python` `Top 100 Liked Questions`

# 23. Merge k Sorted Lists

## [題目來源: ] https://leetcode.com/problems/merge-k-sorted-lists/

## 題目:
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.

#### [圖片來源] https://leetcode.com/problems/merge-k-sorted-lists/

## 解題想法:
priority Queue存每個list的head
依序pop權重最小的

## Python:

from heapq import heappush,heappop
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)
        
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        #time :O(N*K log(K))
        que=[]
        #que存入每個list的head node
        for i in range(len(lists)):
            if lists[i]: #裡面的子list串若非空
                heappush(que,(lists[i].val,i)) #(元素值,來自哪個list編號)
                lists[i]=lists[i].next
        dummy=ListNode(0)
        cur=dummy
        while que:
            val,i=heappop(que) #踢出最小值
            cur.next=ListNode(val)
            cur=cur.next
            #將該i編號的list取出下個next加入heap繼續比較
            if lists[i]:
                heappush(que,(lists[i].val,i))
                lists[i]=lists[i].next
        return dummy.next

head1=ListNode(1)
head1.insert(4)
head1.insert(5)

head2=ListNode(1)
head2.insert(3)
head2.insert(4)

head3=ListNode(2)
head3.insert(6)

lists=[]
lists.extend([head1,head2,head3])

result=Solution()
ans=result.mergeKLists(lists)
ans.printList()