LeetCode 21. 合并两个有序链表

文章目录

• 前言
• 题目
• 题解
• NO1：虚拟头节点+双链表比较插入
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为LeetCode 热题 HOT 100专题。

---

题目

题目来源leetcode

leetcode地址：21. 合并两个有序链表，难度：简单。

题目描述(摘自leetcode)：

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

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
 
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

---

题解

NO1：虚拟头节点+双链表比较插入

思路：对于两个链表都设置一个头节点，比对两个链表的每个值来将值小的插入到新节点中。

代码：时间复杂度:O(n)、空间复杂度O(n)

//示例：[1,2,4]  [1,3,4]  => [1,1,2,3,4,4]
//虚拟头节点+双链表比较插入
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //定义两个虚拟头节点
    ListNode root1 = new ListNode(-1, l1);
    ListNode root2 = new ListNode(-1, l2);
    //新节点
    ListNode root = new ListNode(-1);
    ListNode cur = root;
    while (root1.next != null && root2.next != null) {
        ListNode newNode = null;
        if (root1.next.val >= root2.next.val) {
            newNode = new ListNode(root2.next.val);
            root2 = root2.next;
        } else {
            newNode = new ListNode(root1.next.val);
            root1 = root1.next;
        }
        cur.next = newNode;
        cur = newNode;
    }
    //处理剩余节点
    if (root1.next != null) {
        cur.next = root1.next;
    }
    if (root2.next != null) {
        cur.next = root2.next;
    }
    return root.next;
}

---

参考文章

[1]. leetcode题解

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.11.10