23. Merge k Sorted Lists

【Description】

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

【Idea】
暴力法
直接将list内所有列表元素加入到指定list，排序后生成新链表

借用堆栈
将三个顶点所在的list依次加入，每次按堆的插入进行排序，链表各自head后移；
当某一坐标下的链表遍历完全后，删除该链表；
直至list为空

【Solution】

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# sulution 1
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        nums = []
        for temp_head in lists:
            while temp_head:
                nums.append(temp_head.val)
                temp_head = temp_head.next
        nums.sort()
        head = ListNode(0)
        prev = head
        for i in nums:
            curr = ListNode(i)
            prev.next = curr
            prev = prev.next
        return head.next

# solution2
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        from heapq import heappush, heappop, heapreplace, heapify
        prev = head = ListNode(0)
        h = [(head.val, i, head) for i,head in enumerate(lists) if head]
        heapify(h)
        while h:
            v, index, n = h[0]
            if n.next:
                heapreplace(h, (n.next.val, index, n.next))
            else:
                heappop(h)
            prev.next = n
            prev = prev.next
        return head.next