leetcode hot100 合并k个升序链表

代码

测试用例

测试用例

测试结果

23. 合并 K 个升序链表

已解答

困难

相关标签

相关企业

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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 = [[]]
输出：[]

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

class Solution(object):
    # def getMaxIndex(self,listx):
    #     tmp = [node.val for node in listx]
    #     return tmp.index(min(tmp))

    def mergeTwoLists(self,listA,listB):
        prev = ListNode()
        cur = prev
        while listA and listB:
            if listA.val<listB.val:
                cur.next = listA
                cur = listA
                listA = listA.next
            else:
                cur.next = listB
                cur = listB
                listB = listB.next
        if listA == None:
            cur.next = listB
        if listB == None:
            cur.next = listA
        return prev.next

    def mergeKLists(self, lists):
        """
        :type lists: List[Optional[ListNode]]
        :rtype: Optional[ListNode]
        """
        # 我这个时间复杂度是k**2n，空间复杂度是k
        # pointers = []
        # for i in lists:
        #     if i==None:
        #         continue
        #     else:
        #         pointers.append(i)
        # prev = ListNode(-float('inf'),None)
        # cur = prev
        # while pointers!=[]:
        #     # 得到pointers里面的最大值
        #     # 然后把prev.next设置成这个最大值
        #     # 把这个最大值设置成他的next
        #     # 如果最大值的next是None了，直接pop这个最大值
        #     # 否则继续，直到pointers里面没有东西为止
        #     tmp = pointers[self.getMaxIndex(pointers)]
        #     cur.next = tmp
        #     cur = tmp
        #     if tmp.next==None:
        #         del pointers[self.getMaxIndex(pointers)]
        #     else:
        #         pointers[self.getMaxIndex(pointers)] = tmp.next
        # return prev.next

        # 使用分治算法的思想
        # 最小问题是两个链表合并，是n时间，1空间
        # 使用分治之后是logk *n 时间，logk空间

        m = len(lists)
        if m == 2:
            return self.mergeTwoLists(lists[0],lists[1])
        if m == 1:
            return lists[0]
        if m==0:
            return None
        return self.mergeTwoLists(self.mergeKLists(lists[:m/2]),self.mergeKLists(lists[m/2:]))

        

这个很简单，考虑合并两个链表，然后使用归并排序