Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【刷穿 LeetCode】21. 合并两个有序链表(简单)

【刷穿 LeetCode】21. 合并两个有序链表(简单)

作者头像
宫水三叶的刷题日记
发布于 2021-02-20 01:36:11
发布于 2021-02-20 01:36:11
29200
代码可运行
举报
运行总次数:0
代码可运行

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:l1 = [], l2 = []
输出:[]

示例 3:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1l2 均按 非递减顺序 排列

双指针解法(哨兵技巧)

哨兵技巧我们之前在「2. 两数相加」讲过啦,让三叶来帮你回忆一下:

做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。

由于两条链表本身就是有序的,只需要在遍历过程中进行比较即可:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;    
        if (l2 == null) return l1;
                
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            } 
        }
        
        while (l1 != null) {
            cur.next = l1;
            cur = cur.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            cur.next = l2;
            cur = cur.next;
            l2 = l2.next;
        }
        
        return dummy.next;
    }
}
  • 时间复杂度:对两条链表扫描一遍。复杂度为 O(n)
  • 空间复杂度:O(1)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.21 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 21/1916

为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-01-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
​LeetCode刷题实战21:合并两个有序链表
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/01/19
2720
​LeetCode 21:合并两个有序链表 Merge Two Sorted Lists
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
爱写bug
2019/08/01
4100
21 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
木瓜煲鸡脚
2021/01/18
3210
21 合并两个有序链表
合并两个有序链表(leetcode21)
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
Vincent-yuan
2021/03/04
4150
合并两个有序链表(leetcode21)
LeetCode97|合并两个有序链表
这道题理解起来还是比较容易的对吧,两两比较,然后将较小的数据挂载dummyNode节点后面,这就是使用哨兵节点的好处,一般链表都或多或少的增加一个哨兵节点来处理数据。
码农王同学
2020/10/14
3270
LeetCode - 合并两个有序链表
原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/
晓痴
2019/08/16
4010
LeetCode - 合并两个有序链表
【刷穿 LeetCode】24. 两两交换链表中的节点(中等)
做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。
宫水三叶的刷题日记
2021/02/20
3170
【刷穿 LeetCode】2. 两数相加(中等)
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
宫水三叶的刷题日记
2021/02/20
2780
【刷穿 LeetCode】23. 合并K个升序链表(困难)
做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。
宫水三叶的刷题日记
2021/02/20
3490
【每日leetcode】4.合并有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
一条coding
2021/08/12
3810
【每日leetcode】4.合并有序链表
LeetCode 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
freesan44
2020/06/08
2510
LeetCode题解—两个有序链表合并
关于空间复杂度,有可能有的朋友会觉得用到了m+n长度的链表?所以空间复杂度也是O(m+n)?
码上积木
2021/02/08
2.2K0
LeetCode题解—两个有序链表合并
LeetCode-21 合并两个有序链表
今天我们学习第21题合并两个有序链表,这是一道简单题。下面我们看看这道题的题目描述。
用户3470542
2019/06/26
3970
LeetCode-21 合并两个有序链表
【力扣刷题】21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  
jayjay
2022/11/02
2810
【力扣刷题】21. 合并两个有序链表
21. 合并两个有序链表
将两个升序链表合并为一个新的 「升序」 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
chuckQu
2022/08/19
1840
用最简单的「链表」题向你介绍「哨兵」技巧 ...
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。
宫水三叶的刷题日记
2021/02/26
7520
LeetCode - #21 合并两个有序链表(Top 100)
LeetCode 算法到目前我们已经更新了 20 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。
Swift社区
2022/02/08
2210
LeetCode - #21 合并两个有序链表(Top 100)
每日一刷:合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
乐心湖
2021/03/02
2620
每日一刷:合并两个有序链表
【刷穿 LeetCode】25. K 个一组翻转链表(困难)
做有关链表的题目,有个常用技巧:添加一个虚拟头结点(哨兵),帮助简化边界情况的判断。
宫水三叶的刷题日记
2021/02/20
4490
☆打卡算法☆LeetCode 21、合并两个有序链表 算法解析
链接:21. 合并两个有序链表 - 力扣(LeetCode) (leetcode-cn.com)
恬静的小魔龙
2022/08/07
2170
☆打卡算法☆LeetCode 21、合并两个有序链表  算法解析
相关推荐
​LeetCode刷题实战21:合并两个有序链表
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验