心路历程：

第一反应是直接暴力求解出来，因为题中也没有关于复杂度的要求。写完发现竟然也通过了，后来发现这道题本来考察的是分治算法，不过能解决问题就行吧。

从评论区看到了一句话很有意思：链表的题能暴力做出来的基本都能通过，感觉这句话很有含金量，希望面试的时候能遇到这道题。

解法一：暴力

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        res = []
        for eachlink in lists:
            while eachlink:
                res.append(eachlink.val)
                eachlink = eachlink.next
        res.sort()
        duhead = ListNode()
        t = duhead
        for eve in res:
            newnode = ListNode(eve)
            duhead.next = newnode
            duhead = duhead.next
        return t.next

解法二：堆（每次都选择第一列最小的元素排队去）

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        l = []
        n = len(lists)
        for i in range(n):
            if lists[i]:
                heapq.heappush(l, (lists[i].val, i))
        dummy_node = ListNode(-1)
        cur = dummy_node
        while l:
            _, index = heapq.heappop(l)
            # 定位到此时应该出列的那个链表的头结点
            head = lists[index]
            # 开始“穿针引线”
            cur.next = head
            cur = cur.next
            # 同样不要忘记判断到链表末尾结点的时候
            if head.next:
                # 刚刚出列的那个链表的下一个结点成为新的链表头结点加入优先队列
                heapq.heappush(l, (head.next.val, index))
                # 切断刚刚出列的那个链表的头结点引用
                lists[index] = head.next
                head.next = None
        return dummy_node.next