题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
该题采用两种方式解决,第一种递归:
/*
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这个首节点就可以了.
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
