[每日一题] 第十八题：合并两个排序的链表

题目描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

题解

方法一：遍历

解题思路：

根据题目描述，链表 l1，l2 是递增的，因此容易想到使用双指针 l1 和 l2 遍历两链表，根据 l1.val 和 l2.val 的大小关系确定节点添加顺序，两节点指针交替前进，直至遍历完毕。
引入伪头结点： 由于初始状态合并链表中无节点，因此循环第一轮无法将节点添加到合并链表中，解决方案：初始化一个辅助节点 dum 作为合并链表的伪头节点，将各节点添加至 dum 之后。

[每日一题] 第十八题：合并两个排序的链表

算法流程：

初始化： 伪头节点 dum，节点 cur 指向 dum。
循环合并： 当 l1 或 l2 为空时跳出；
1. 当 l1.val < l2.val 时：cur 的后继节点指定为 l1，并 l1 向前一步；
2. 当 l1.val >= l2.val 时：cur 的后继节点指定为 l2，并 l2 向前走一步；
3. 节点 cur 向前走一步，即 cur = cur.next
合并剩余尾部： 跳出时有两种挺狂，即 l1 为空或 l2 为空。
1. 若 l1 != null：将 l1 添加至节点 cur 之后；
2. 否则：将 l2 添加至节点 cur 之后。
返回值： 合并链表在伪头节点 dum 之后，因此返回 dum.next 即可。

代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode(0), cur = dum;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }
            else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dum.next;
    }
}

复杂度

时间复杂度：O(M+N)，M，N 分别为链表 l1，l2 的长度，合并操作需遍历两链表。
空间复杂度：O(1)：节点引用 dum，cur 使用常数大小的额外空间。

来源

作者：jyd
链接：leetcode-cn.com/problems/he-bing-l...
来源：力扣（LeetCode）

来源

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/he-bing-l...

leetcode 简单

本作品采用《CC 协议》，转载必须注明作者和本文链接

DRose

版主 484 声望

暂无个人描述~

0 人点赞

讨论数量: 0

(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

[每日一题] 第十八题：合并两个排序的链表

题目描述

题解

方法一：遍历

代码

复杂度

来源

来源

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

[每日一题] 第十八题：合并两个排序的链表

题目描述

题解

方法一：遍历

代码

复杂度

来源

来源

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录