leetcode刷题-合并k个有序链表

leetcode刷题-合并k个有序链表

Scroll Down

题目描述

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

示例:

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

解题思路

1. 两两归并

刚开始拿到这道题目,我想到的方法就是先将第一条链表和第二条链表归并,得到一条新的有序链表,然后再将新的链表和第三条链表归并,依次类推,直到所有链表都被合并。

具体代码如下:

class ListNode:
    """
    单链表结点
    """

    def __init__(self, x):
        self.val = x  # 数据域
        self.next = None  # 指针域

def merge_k_lists(lists: List[ListNode]) -> ListNode:
    """
    合并 k 个排序链表,返回合并后的排序链表。
    :param lists: 单链表列表
    :return:单链表
    """
    c = ListNode(None)
    if not lists: # 链表为空
        return c.next
    if len(lists) == 1: # 链表长度为 1
        return lists[0]
    p = lists[0]
    r = c  # r 指向 c
    # 通过循环两两归并链表
    for i in range(1, len(lists)):
        q = lists[i] # q 指向链表数组中链表的头结点
        while p and q:
            if p.val < q.val:
                r.next = p
                p = p.next
                r = r.next
            else:
                r.next = q
                q = q.next
                r = r.next
        if p is not None: # 将剩下的结点直接拼接到新链表的后面
            r.next = p
        if q is not None:
            r.next = q
        p = c.next # p 指向新链表的头结点的下一个结点
        r = c # r 指向新链表的头结点
    return c.next

2. 优先队列

优先队列与普通队列不同,普通队列是按照进入队列的顺序先进先出,但是优先队列是按照数值大小先进先出。

优先队列的底层是通过(二叉树)来实现的,对于升序优先队列,每次入队,最小的元素都会位于队头,每次出队,都会将最小值删除。

因此,我们可以通过优先队列来处理这个问题,先将所有链表中的元素依次入队,再依次出队,由于每次出队的都是队中最小值,那么出队之后的顺序就是递增有序。

关于优先队列的具体介绍和实现,可以参考下面这篇博文。

数据结构与算法(4)——优先队列和堆

具体代码如下:

python 中自带了 heapq 模块,它的底层是基于最小堆来实现的,符合升序优先队列的条件,直接调用即可。

class ListNode:
    """
    单链表结点
    """

    def __init__(self, x):
        self.val = x  # 数据域
        self.next = None  # 指针域

def merge_k_lists(lists: List[ListNode]) -> ListNode:
    heap = []
    import heapq # 导入 heapq 模块
    for node in lists: # 遍历链表数组,构建优先队列
        r = node # r 指向当前结点
        while r:
            heapq.heappush(heap, r.val) # 入队
            r = r.next
    c = ListNode(None) # 创建新头结点
    curr = c # curr 指向头结点 c
    while heap: # 遍历队列
        new = ListNode(heapq.heappop(heap)) # 出队,创建新结点 new
        curr.next = new # 通过尾插法构建新链表
        curr = new
    return c.next # 头结点不保存数据,返回头结点的下一个结点

后续

1. python 实现优先队列

class PriorityQueue:
    """
    (升序)优先队列
    """

    def push(self, queue, val):
        """
        入队
        :param queue: 队列
        :param val:数据
        """
        queue.append(val)
        self._sift_up(queue, 0)

    def pop(self, queue):
        """
        出队
        :return:最小值
        """
        min_val = queue[0]  # 获取堆顶元素(最小值)
        n = len(queue)
        queue[0], queue[n - 1] = queue[n - 1], queue[0]  # 交换堆顶元素和末尾元素
        queue.pop()  # 删除末尾元素
        self._sift_down(queue, 0)  # 向下调整优先队列
        return min_val

    @staticmethod
    def _sift_up(queue, start):
        """
        向上调整优先队列
        :param queue: 队列
        :param start: 开始下标
        """
        n = len(queue)
        child = n - 1
        parent = child // 2
        while child >= start and queue[child] < queue[parent]:
            queue[parent], queue[child] = queue[child], queue[parent]
            child = parent
            parent = (child - 1) // 2

    @staticmethod
    def _sift_down(queue, start):
        """
        向下调整队列
        :param queue: 队列
        :param start: 开始下标
        """
        n = len(queue)
        parent = start
        child = 2 * parent + 1
        while child < n:
            if child + 1 < n and queue[child + 1] < queue[child]:
                child += 1
            if queue[parent] < queue[child]:
                break
            queue[parent], queue[child] = queue[child], queue[parent]
            parent = child
            child = 2 * parent + 1