leetcode 23

方法一

# 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]:
        tempArray = list()
        for l in lists:
            while l:
                tempArray.append(l.val)
                l = l.next
        tempArray.sort(reverse = False)

        resNode = tempNode = ListNode(0)

        for t in tempArray:
            tempNode.next = ListNode(t)
            tempNode = tempNode.next
        
        return resNode.next

方法二

#还有一个类似方法一的做法，就是通过python的一个库-->heapq来实现push和pop操作，其中弹出的元素为堆中最小的element

#heappush(heap, item) # pushes a new item on the heap

#item = heappop(heap) # pops the smallest item from the heap

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists or len(lists) == 0:
            return None
        import heapq
        heap = []
        # 首先 for 嵌套 while 就是将所有元素都取出放入堆中
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        dummy = ListNode(None)
        cur = dummy
        # 依次将堆中的元素取出(因为是小顶堆，所以每次出来的都是目前堆中值最小的元素），然后重新构建一个列表返回
        while heap:
            temp_node = ListNode(heappop(heap))
            cur.next = temp_node
            cur = temp_node
            #print(heap)
        return dummy.next