作者简介：大家好，我是smart哥，前中兴通讯、美团架构师，现某互联网公司CTO
联系qq：184480602，加我进群，大家一起学习，一起进步，一起对抗互联网寒冬
学习必须往深处挖，挖的越深，基础越扎实！
阶段1、深入多线程
阶段2、深入多线程设计模式
阶段3、深入juc源码解析
阶段4、深入jdk其余源码解析
阶段5、深入jvm源码解析
码哥源码部分
码哥讲源码-原理源码篇【2024年最新大厂关于线程池使用的场景题】
码哥讲源码【炸雷啦！炸雷啦！黄光头他终于跑路啦！】
码哥讲源码-【jvm课程前置知识及c/c++调试环境搭建】
码哥讲源码-原理源码篇【揭秘join方法的唤醒本质上决定于jvm的底层析构函数】
码哥源码-原理源码篇【Doug Lea为什么要将成员变量赋值给局部变量后再操作？】
码哥讲源码【你水不是你的错,但是你胡说八道就是你不对了！】
码哥讲源码【谁再说Spring不支持多线程事务，你给我抽他！】
终结B站没人能讲清楚红黑树的历史，不服等你来踢馆！
打脸系列【020-3小时讲解MESI协议和volatile之间的关系，那些将x86下的验证结果当作最终结果的水货们请闭嘴】
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
该题采用两种方式解决,第一种递归:
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null) {
return list2;
}
if(list2==null) {
return list1;
}
if(list1.val>=list2.val) {
list2.next=Merge(list1, list2.next);
return list2;
}else {
list1.next=Merge(list1.next,list2);
return list1;
}
}
}
递归方式相对来说比较简单,容易理解,但是解释起来比较麻烦,以下将对递归进行解释:
递归的话,我个人喜欢把整个方法看成一个整体,
首先两个非空链表进入到if判断,
假设第一次list1.val的值大于等于list2.val的值,是不是当前list2作为第一个结点,这个理解了的话,是不是现在整条合并链就确定了第一个结点了,那么整体思想来看,后面我们只需要对list1和list2.next两条链表进行排序了;如果这个理解了,那再一次调用这个方法的时候,又是一样的判断逻辑,一直调用,直到为null就可以了,其他的就不多做判断了.
第二种方法:
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
ListNode mergeHead = null;
ListNode current = null;
while(list1!=null && list2!=null){
if(list1.val <= list2.val){
if(mergeHead == null){
mergeHead = current = list1;
}else{
current.next = list1;
current = list1;
}
list1 = list1.next;
}else{
if(mergeHead == null){
mergeHead = current = list2;
}else{
current.next = list2;
current = list2;
}
list2 = list2.next;
}
}
if(list1 == null){
current.next = list2;
}else{
current.next = list1;
}
return mergeHead;
}
}
对于以上代码进行解释:
假设list1中的数据如图所示:
list2中的数据如图所示:
进行第一次比较,list1.val(1) < list2.val(2),因为是第一个结点,所以mergeHead =null,将当前结点 list1 赋给mergeHead和current,且mergeHead 就是我们要返回的合并链表的头部.我们真正操作的是current这条链表(这里面的道理就是,mergeHead指向current这条链表的头部,而current就是我们合并的链表.但是因为current该链表只能从当前结点往下读,所以我们需要确定一个头结点),然后让list1指向下一位继续进行比较---> list1=list1.next
list1的数据如图所示:
进行第二次比较,list1.val(4)>list2.val(2),使得current.next=list2,让current=list2(让current指向list2.val(3)的地址),然后list2=list2.next,使得list2指向list2.val(6)的地址:
list2现在的数据如图所示:
中间省略重复的,一直到比较list1.val(10)<list2.val(11),令current.next=list1,让current=list1(让current指向list1.val(10)的地址),然后list1 =list2.next;循环发现list1现在为空,退出循环,然后进行判断将list2.val(11)这个地址结点加进去.
最后直接返回mergeHead这个首节点就可以了.
