剑指offer JZ16：合并两个排序的链表（伪头节点，清晰图解）_l1.vall java-程序员宅基地

技术标签：算法 java 链表新星计划 # 剑指offer 数据结构

解题思路：

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

算法流程：

1.初始化：伪头节点 dum ，节点 cur 指向 dum 。

2.循环合并：当l1、l2为空时跳出；

当 l_1.val <= l_2.vall 时： cur的后继节点指定为 l1，并l1向前走一步；
当 l_1.val >= l_2.vall 时： cur的后继节点指定为 l2，并l2 向前走一步；
节点 curcur 向前走一步，即 cur = cur.next。

3.合并剩余尾部：跳出时有两种情况，即l1 为空或l2为空。

若 ll1不等于null ：将l1添加至节点 cur 之后；
否则：将l2添加至节点 curcur 之后。

4.返回值：合并链表在伪头节点 dum 之后，因此返回 dum.next 即可。

过程图解

复杂度分析：

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

代码：

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 ? l2 : l1;
        return dum.next;
    }
}

本文链接：https://blog.csdn.net/weixin_44589991/article/details/117375999

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【VMW】【Lunix】虚拟机ping出现From 192.168.1.10: icmp_seq=1 Redirect Network(New nexthop: 192.168.1.1)问题_来自 192.168.158.1 icmp_seq=2 redirect host(新的下一跳: 1-程序员宅基地

文章浏览阅读1.7k次。问题虚拟机中ping 百度或者网关，可以访问外网，连接正常但是会出现如下问题：root@yuxy:~# ping 192.168.23.1PING 192.168.23.1 (192.168.23.1) 56(84) bytes of data.From 192.168.23.213: icmp_seq=1 Redirect Network(New nexthop: 192.168.23.1)64 bytes from 192.168.23.1: icmp_seq=1 ttl=255 time=1_来自 192.168.158.1 icmp_seq=2 redirect host(新的下一跳: 192.168.158.136)

使用jmespath第三方模块提取json数据_jmespath取json的下标-程序员宅基地

文章浏览阅读4.7k次，点赞2次，收藏11次。在工作中经常需要查找json里面的某个key的值，如果json层级太长，使用字典自带的get方法，比较麻烦。这里演示一下第三方模块jmespath提取json键、值。pip install jmespath一、基本操作查询key对应的valueimport jmespathsource = {"a": "foo", "b": "bar", "c": "baz"}result = ..._jmespath取json的下标

汇编指令学习与总结CMP，TEST，JE，JNZ，JNE，LEA，MOVE，SUB，INC,DEC,ADD,MUL,DIV,JGE，JB ,CQD_汇编 je-程序员宅基地

文章浏览阅读3w次，点赞41次，收藏209次。所有的汇编都是我零基础逆向微信汇编的指令边玩边学（左边有机器码，自己可以查位置）如有不对的地方请指出注明:一些指令的英文单词，并非官方，只是为了好记好理解cmp【compare】指令进行比较两个操作数的大小例:cmp oprd1,oprd2为第一个操作减去第二个操作数,但不影响第两个操作数的值,它影响flag的CF，ZF，OF，AF，PF.66E9419E 66:833..._汇编 je

论坛集_77论坛-程序员宅基地

文章浏览阅读1.3w次。000013 001http://people.sina.com.cn/forum.html新浪网论坛 000015 002http://club.sohu.com/搜狐社区 000020 003http://bj.163.com/网易北京社区 000043 004http://bbs.tom.com/bbs.phpTOM海云天论坛 000143 005http://bbs.china.com/中_77论坛

python-字符串中使用%%有什么作用？%操作符的各种用法小结_python %%-程序员宅基地

文章浏览阅读1.3w次，点赞6次，收藏43次。python-字符串中使用%%有什么作用？%操作符的各种用法小结_python %%

随便推点

Pluto SDR环境搭建libiio/libad9361-iio/GNU Radio/gr-iio(Ubuntu)_gnuradio 3.8.2 如何支持adalm pluto-sdr windows-程序员宅基地

文章浏览阅读784次，点赞11次，收藏10次。ADI前些年推出的ADALM-PLUTO SDR设备由于其轻便灵活的特点，外加价格相比于专业无线电相当实惠，受到了很多开源社区的欢迎，也诞生了许多的应用，如跟踪GPS、伪造GPS实现硬件级虚拟定位、电子钥匙重发攻击等（这些实际上HackRF做的更多）。同时对于学习通信的师生和对无线电感兴趣的业余玩家，也是个很不错的选择。国内购买纯原版Pluto SDR有些困难，但好在国内也有很多企业或团队基于某些成熟的SDR平台衍生出的性能更强，适用固件更多的软件无线电平台，价格也并非难以承受。_gnuradio 3.8.2 如何支持adalm pluto-sdr windows

SIM卡、USIM卡、UICC卡、eSIM卡的区别_uhimpc-程序员宅基地

文章浏览阅读2.8k次。SIM的英文全称是“Subscriber Identity Module”，即“用户身份模块”。它的主要作用是在移动终端设备与网络通讯时提供身份识别信息及存储数据，大家比较容易理解的就是我们的电话号码（身份识别信息）是与SIM卡直接绑定的，还有SIM卡还可以存储电话号码、短消息等数据。COMPRION公司的测试用SIM卡现在的3G与4G移动系统里，准确地说SIM是一个应用的概念，..._uhimpc

{技术操作} Vue tab 切换点击栏目背景色改变，内容也改变_vue3el-tabs选中时tabs页背景色改变-程序员宅基地

文章浏览阅读289次，点赞4次，收藏3次。/这是每个tab内容不同的情况下使用，(如果每个tab内部内容一样底下可直接v-for循环就行了 )工业内部内容制造内部内容服务内部内容其他内部内容css// 选中后的效果js。_vue3el-tabs选中时tabs页背景色改变

VUE实现一个好看半透明登陆界面（附源码）_vue登录界面主题样式-程序员宅基地

文章浏览阅读5.5k次，点赞4次，收藏22次。欢迎使用消防员定位系统 @西南交通大学 | 邓平老师团队</el-header><el-main> <div id="login_box"> <h2>消防员系统登录</h2> <div id="form"> <div id="input_box"> <i class="fa fa-user" aria-hidden="tr..._vue登录界面主题样式

MySQL 1045登录失败完美解决方案_failed to initialize database, got error error 104-程序员宅基地

文章浏览阅读4.4w次，点赞5次，收藏27次。登录MySQL数据库出现：Error 1045错误时（如下图），就表明输入的用户名或密码错误被拒绝访问了，最简单的解决方法就是将MySQL数据库卸载然后重装，但这样的缺点就是就以前的数据库中的信息将丢失，解决的方法应该有多种，这里推荐大家使用一种原理通过，操作简单的方法，适用于windows以及linux平台。 MySQL 1045错误如图：[plain] view plain ..._failed to initialize database, got error error 1045 (28000): access denied f

第一款个人应用——《不做手机控》——终于上线啦！_不做手机控是哪个公司的-程序员宅基地

文章浏览阅读9.3k次，点赞14次，收藏10次。从事Android已经大半年了，居然没有一款自己的产品，真是惭愧啊，不过经过这一个半月的艰苦奋斗，我人生中第一个个人Android应用终于诞生了！叫——不做手机控。感谢老婆大人起的好名字。这是下载连接：点击打开链接，请朋友们多提意见和建议！回想这半个月，还真不容易，每天下班继续码代码是最基本的，还要一个人兼任开发、产品、设计、测试等多项工作。其实产品、测试的工作还好说，毕竟平时接触的多，赶鸭子上架..._不做手机控是哪个公司的