每日一道算法之--合并K个排序链表

分治优先队列堆

Word count: 763Reading time: 3 min

 2020/03/20   Share

合并K个排序链表

力扣第23题:https://leetcode-cn.com/problems/merge-k-sorted-lists/

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6

暴力算法

把N个数放到一个数组里，再一起排序，O(NlogN)。

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

分治算法

这道题其实和归并排序基本是完全一样的,利用分治思想,将k个链表分成多个两组链表再合并,和归并排序基本一致.

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return 
        n = len(lists)
        if n < 2: return lists[n - 1]
        mid = n // 2
        left = lists[0:mid]
        right= lists[mid:]
        return self.merge(self.mergeKLists(left), self.mergeKLists(right))

    def merge(self, l, r):
        new_node = ListNode(0)
        n = new_node
        while l and r:
            if l.val <= r.val:
                n.next, l = l, l.next
            else:
                n.next, r = r, r.next
            n = n.next
        if l:
            n.next = l
        if r:
            n.next = r
        return new_node.next

复杂度分析

时间复杂度:我们可以在 O(n)的时间内合并两个有序链表，其中 n 是两个链表中的总节点数。将所有的合并进程加起来，我们可以得到时间复杂度为 O(Nlogk),其中 k 是链表的数目。

空间复杂度:没有用到额外的数据结构,可以用O(1)的空间复杂度合并两个链表,所以空间复杂度为O(1)

利用堆(优先队列)实现

由于k个链表是有序的，我们实际上只需要维护k个指针从k个链表的头向尾滑动，每次选取k个链表的表头里的最小加入新的有序链表里。这就可以维护一个最小堆(优先队列)。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        que = [] # curs存K个链表滑动的头指针
        for index, node in enumerate(lists):
                if node!=None:
                    heapq.heappush(que ,(node.val, index))

        dummy_node = ListNode(-1)
        cur = dummy_node
        while que:
            val, index =  heapq.heappop(que)
            cur.next = lists[index]
            cur = cur.next
            lists[index] = lists[index].next
            if lists[index] is not None:
                heapq.heappush(que, (lists[index].val, index))
        return dummy_node.next