合并K个升序链表(LeetCode 23)

这篇具有很好参考价值的文章主要介绍了合并K个升序链表(LeetCode 23)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.问题描述

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

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

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

2.难度等级

Hard。

3.热门指数

★★★★☆

4.解题思路

方法一:顺序合并

我们可以想到一种最朴素的方法,依次将链表数组中的链表与最终结果合并。问题便退化成合并两个有序链表。

如何合并两个有序链表呢?

遍历两个链表选择值较小的结点链接到结果链表中即可。当一个节点被添加到结果链表之后,将对应链表中的节点向后移一位。

为了简化对结果链表边界条件的判断,可以引入哨兵结点。哨兵结点的 Next 指针便是结果链表的头结点。

遍历 list1 或 list2 链表,选择 list1 与 list2 链表当前结点值较小的结点,挂接到结果链表,并将较小结点后移一位。
如果有一个为空,结束遍历,则将未遍历完的链表,直接挂接到结果链表。

时间复杂度: 假设每个链表的最长长度是 n。在第一次合并后,结果链表的长度为 n;第二次合并后,结果链表的长度为 2n,第 i 次合并后,结果链表的长度为 in。第 i 次合并的时间代价是 O(n+(i−1)×n)= O(in),那么总的时间代价为
O ( ∑ i = 1 k ( i × n ) ) = O ( ( 1 + k ) ⋅ k 2 × n ) = O ( k 2 n ) O(\sum_{i = 1}^{k} (i \times n)) = O(\frac{(1 + k)\cdot k}{2} \times n) = O(k^2 n) O(i=1k(i×n))=O(2(1+k)k×n)=O(k2n)
故渐进时间复杂度为 O ( k 2 n ) O(k^2n) O(k2n),其中 k 为链表个数。

空间复杂度: 没有用到与 k 和 n 规模相关的辅助空间,故渐进空间复杂度为 O(1)。

下面以 Golang 为例给出实现。

func merge(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val < temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else {
		temp.Next = temp2
	}
	return dummyHead.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
	var head *ListNode
	for _, l := range lists {
		head = merge(head, l)
	}
	return head
}

方法二:分治合并

可以优化方法一,采用分治的方法进行合并。

  • 将 k 个链表配对并将同一对中的链表合并;
  • 第一轮合并以后, k 个链表被合并成了 k 2 \frac{k}{2} 2k个链表,然后是 k 4 \frac{k}{4} 4k 个链表, k 8 \frac{k}{8} 8k 个链表等等。
    重复这一过程,直到我们得到了最终的有序链表。
  • 重复这一过程,直到我们得到最终的有序链表。

合并K个升序链表(LeetCode 23),LeetCode,合并链表,LeetCode 23
时间复杂度: 考虑递归「向上回升」的过程,每一轮合并的时间复杂度都是 O(kn),需要合并 logk 轮,所以总的时间复杂度是 O(kn*logk)。

空间复杂度: 递归会使用到 O(log⁡k) 空间代价的栈空间。

下面以 Golang 为例给出实现。

func merge(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val < temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else {
		temp.Next = temp2
	}
	return dummyHead.Next
}

func divideMerge(lists []*ListNode, l, r int) *ListNode {
	if l == r {
		return lists[l]
	}

	mid := (l + r) / 2
	// 合并左链表
	lhead := divideMerge(lists, l, mid)
	// 合并右链表
	rhead := divideMerge(lists, mid+1, r)
	// 合并左右链表
	return merge(lhead, rhead)
}

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	return divideMerge(lists, 0, len(lists)-1)
}

方法三:使用优先队列合并

这个方法和前两种方法的思路有所不同,我们需要维护当前每个链表没有被合并的元素的最前面一个,kkk 个链表就最多有 kkk 个满足这样条件的元素,每次在这些元素里面选取 val\textit{val}val 属性最小的元素合并到答案中。在选取最小元素的时候,我们可以用优先队列来优化这个过程。

时间复杂度: 考虑优先队列中的元素不超过 k 个,那么插入和删除的时间代价为 O(log⁡k),这里最多有 kn 个结点,对于每个结点都被插入删除各一次,故总的时间代价为 O(kn*log⁡k)。

**空间复杂度:**这里用了优先队列,优先队列中的元素不超过 k 个,故渐进空间复杂度为 O(k)。

下面以 C++ 为例给出实现。

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };

    priority_queue <Status> q;

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

参考文献

23. 合并K 个升序链表 - LeetCode文章来源地址https://www.toymoban.com/news/detail-805331.html

到了这里,关于合并K个升序链表(LeetCode 23)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣每日一题】23. 合并 K 个升序链表 &暴力法-快排 & 8.12打卡

    合并 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 ] 将它们合并到一个有序

    2024年02月13日
    浏览(34)
  • 2023-08-12 LeetCode每日一题(合并 K 个升序链表)

    点击跳转到题目位置 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 示例 2: 示例 3:

    2024年02月13日
    浏览(39)
  • 【LeetCode 算法】Merge k Sorted Lists 合并 K 个升序链表

    给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 k = = l i s t s . l e n g t h 0 = k = 1 0 4 0 = l i s t s [ i ] . l e n g t h = 500 − 1 0 4 = l i s t s [ i ] [ j ] = 1 0 4 l i s t s [ i ] 按升序排列 l i s t s [ i ] . l e n g t h 的总和不超过 1 0

    2024年02月13日
    浏览(33)
  • 合并 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: 输入

    2024年02月02日
    浏览(36)
  • 合并 k 个升序的链表

    C++——优先级队列(priority_queue)_c++priority_queue__好好学习的博客-CSDN博客 那么这道题就可以用小顶堆 分治的思想,归并排序的思想

    2024年02月10日
    浏览(47)
  • 合并两个有序链表,将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    题记: 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入 :l1 = [1,2,4], l2 = [1,3,4] 输出 :[1,1,2,3,4,4] 示例 2: 输入 :l1 = [], l2 = [] 输出 :[] 示例 3: 输入 :l1 = [], l2 = [0] 输出 :[0] 提示: 两个链表的节点数

    2024年02月07日
    浏览(62)
  • 面试热题(合并K个升序链表)

    给定一个链表数组,每个链表都已经按升序排列。 请将所有链表合并到一个升序链表中,返回合并后的链表。        这道题看似困难题,其实还是比较容易好想的,我们可以维护一个优先最小队列,然后声明一个虚拟头结点,每次出一个最小的节点挂载在已经挂载节点的后

    2024年02月12日
    浏览(31)
  • 【力扣每日一题】2023.8.12 合并K个升序链表

    目录 题目: 示例: 分析: 代码: 题目给我们一个链表数组,数组里的链表都是升序的,让我们合并这些链表,要求合并之后还是升序的。 最简单最直观的做法就是遍历整个数组,把每个链表的节点都取出来塞到一个容器里,然后对容器进行升序排序,接着按顺序重新串连

    2024年02月13日
    浏览(40)
  • 【Leetcode】反转链表 合并链表 相交链表 链表的回文结构

      目录 一.【Leetcode206】反转链表 1.链接 2.题目再现  3.解法A:三指针法 二.【Leetcode21】合并两个有序链表 1.链接 2.题目再现  3.三指针尾插法 三.【Leetcode160】相交链表 1.链接 2.题目再现 3.解法 四.链表的回文结构 1.链接 2.题目再现  3.解法 1.链接 反转链表 2.题目再现  3.解法

    2024年02月02日
    浏览(48)
  • Leetcode 21. 合并两个有序链表

    题目链接:https://leetcode.cn/problems/merge-two-sorted-lists/description/ 两个链表都是升序链表,新建一个链表,引入伪头节点作为辅助节点,将各节点添加到伪节点之后,再用一个cur节点指向新链表的末尾 遍历两个链表,对比每个节点值,将更小的链表节点加入到新链表中 如果其中一

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包