# 给你一个链表数组，每个链表都已经按升序排列。
#
#  请你将所有链表合并到一个升序链表中，返回合并后的链表。
#
#
#
#  示例 1：
#
#  输入：lists = [[1,4,5],[1,3,4],[2,6]]
# 输出：[1,1,2,3,4,4,5,6]
# 解释：链表数组如下：
# [
#   1->4->5,
#   1->3->4,
#   2->6
# ]
# 将它们合并到一个有序链表中得到。
# 1->1->2->3->4->4->5->6
#
#
#  示例 2：
#
#  输入：lists = []
# 输出：[]
#
#
#  示例 3：
#
#  输入：lists = [[]]
# 输出：[]
#
#
#
#
#  提示：
#
#
#  k == lists.length
#  0 <= k <= 10^4
#  0 <= lists[i].length <= 500
#  -10^4 <= lists[i][j] <= 10^4
#  lists[i] 按 升序 排列
#  lists[i].length 的总和不超过 10^4
#
#  Related Topics 堆 链表 分治算法


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        temp = ListNode(None)
        res = temp

        while heap:
            # temp.next = ListNode(heap.pop())
            temp.next = ListNode(heapq.heappop(heap))
            temp = temp.next
        return res.next

        # heap = []
        # for node in lists:
        #     while node:
        #         heapq.heappush(heap, node.val)
        #         node = node.next
        #
        # temp = ListNode(-1)
        # head = temp
        # while heap:
        #     smallestNode_val = heapq.heappop(heap)
        #     temp.next = ListNode(smallestNode_val)
        #     temp = temp.next
        #
        # return head.next

# leetcode submit region end(Prohibit modification and deletion)

64935cbd9b6d1477baebd943ba1d35e6ae500afd
<mask token>

<mask token>


class Solution(object):

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        temp = ListNode(None)
        res = temp
        while heap:
            temp.next = ListNode(heapq.heappop(heap))
            temp = temp.next
        return res.next

class ListNode:
    <mask token>


class Solution(object):

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        temp = ListNode(None)
        res = temp
        while heap:
            temp.next = ListNode(heapq.heappop(heap))
            temp = temp.next
        return res.next

class ListNode:

    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        temp = ListNode(None)
        res = temp
        while heap:
            temp.next = ListNode(heapq.heappop(heap))
            temp = temp.next
        return res.next

# 给你一个链表数组，每个链表都已经按升序排列。
#
#  请你将所有链表合并到一个升序链表中，返回合并后的链表。
#
#
#
#  示例 1：
#
#  输入：lists = [[1,4,5],[1,3,4],[2,6]]
# 输出：[1,1,2,3,4,4,5,6]
# 解释：链表数组如下：
# [
#   1->4->5,
#   1->3->4,
#   2->6
# ]
# 将它们合并到一个有序链表中得到。
# 1->1->2->3->4->4->5->6
#
#
#  示例 2：
#
#  输入：lists = []
# 输出：[]
#
#
#  示例 3：
#
#  输入：lists = [[]]
# 输出：[]
#
#
#
#
#  提示：
#
#
#  k == lists.length
#  0 <= k <= 10^4
#  0 <= lists[i].length <= 500
#  -10^4 <= lists[i][j] <= 10^4
#  lists[i] 按 升序 排列
#  lists[i].length 的总和不超过 10^4
#
#  Related Topics 堆 链表 分治算法


# leetcode submit region begin(Prohibit modification and deletion)
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            while node:
                heapq.heappush(heap, node.val)
                node = node.next
        temp = ListNode(None)
        res = temp

        while heap:
            # temp.next = ListNode(heap.pop())
            temp.next = ListNode(heapq.heappop(heap))
            temp = temp.next
        return res.next

        # heap = []
        # for node in lists:
        #     while node:
        #         heapq.heappush(heap, node.val)
        #         node = node.next
        #
        # temp = ListNode(-1)
        # head = temp
        # while heap:
        #     smallestNode_val = heapq.heappop(heap)
        #     temp.next = ListNode(smallestNode_val)
        #     temp = temp.next
        #
        # return head.next

# leetcode submit region end(Prohibit modification and deletion)
