题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
分析
一、递归
不用关注过程，注重结果（代码注释中有具体的视频和递归压栈规律）
二、迭代法
使用哑节点和指针的方式迭代解决
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 解法一：使用递归的方法
// return mergeTwoLists01(list1,list2);
// 解法二：迭代法
return mergeTwoLists02(list1,list2);
}
// 解法一：使用递归；正在的知道什么叫递归
// https://leetcode.cn/problems/merge-two-sorted-lists/solution/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/
// https://www.bilibili.com/video/BV1eb4y1e7SP?spm_id_from=333.337.search-card.all.click&vd_source=3f506dfd7b2a19c74f99363591d70f4c
private static ListNode mergeTwoLists01(ListNode list1, ListNode list2){
// base case 当其中一个链表遍历到最后的时候，直接将另一条未遍历完的链表返回
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
// 判断当前节点的大小，将当前节点小的值指向后驱节点
if(list1.val>list2.val){
// 这时候小的就是前驱节点（list2.next，list1.next）这两个的含义
list2.next=mergeTwoLists01(list1,list2.next);
return list2;
}
list1.next=mergeTwoLists01(list1.next,list2);
return list1;
}
// 解法二：迭代法，使用指针
private static ListNode mergeTwoLists02(ListNode l1, ListNode l2){
// 定义一个哑节点;定义活动指针
ListNode dummy=new ListNode();
ListNode cur=dummy;
// 迭代比较
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
// 进行赋值
cur.next=l1;
// 新链表后移一个节点
cur=cur.next;
// 比较过的链表后移
l1=l1.next;
}else{
// 进行赋值
cur.next=l2;
// 新链表后移一个节点
cur=cur.next;
// 比较过的链表后移
l2=l2.next;
}
}
// 循环结束，有一个为空，直接将新链表进行连接
if(l1!=null){
cur.next=l1;
}else{
cur.next=l2;
}
return dummy.next;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96237.html
