https://leetcode.cn/problems/merge-two-sorted-lists
含 C 和 JAVA 两种语言的题解
1. 题目描述
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入/输出样例：
C
// 样例 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 <= 100l1和l2均按 非递减顺序 排列
2. 【方法一】双指针
一、思路
两个链表 l1、l2 都是递增的，可以想到用双指针 l1 和 l2 遍历两链表，根据 l1.val 和 l2.val 的大小关系确定添加顺序。
两个节点指针交替前进，直到遍历完毕。
因为初始状态下，合并链表（结果链表）中无节点，循环第一轮时无法将节点添加到合并链表中，所以需要初始化一个伪头节点 dum（Dummy Node 的缩写），将各节点添加到 dum 之后。
伪头节点也叫哨兵节点，其 val 值是随便给的，这里用 0 。伪头节点和数据结构中常引入的头节点（Head Node）不一样：
- 伪头节点是辅助性的、临时性的，用完即弃，不作为结果的一部分；
- 而数据结构教材中常提到的头节点，本身是链表的一部分
二、算法流程
- 初始化：伪头节点
dum，节点cur指向dum（在 C 语言里就是让 cur 和 dum 存放相同的内存地址，类似“引用传递”的感觉）。 - 循环合并：当
l1或l2为空时跳出。- 当
l1.val < l2.val时：cur的后继节点指定为l1，并l1向前走一步。 - 当
l1.val >= l2.val时：cur的后继节点指定为l2，并l2向前走一步。 - 节点
cur向前走一步，即cur = cur.next。
- 当
- 合并剩余尾部：跳出时有两种情况，即
l1为空 或l2为空。- 若
l1 != null：将l1添加至节点cur之后。 - 否则：将
l2添加至节点cur之后。
- 若
- 返回值：合并链表在伪头节点
dum之后，因此返回dum.next即可。
三、代码 & 复杂度分析
C 代码：
C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* dum = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = dum;
while(l1 != NULL && l2 != NULL) {
if (l1->val >= l2->val) {
cur->next = l2;
l2 = l2->next;
}
else {
cur->next = l1;
l1 = l1->next;
}
cur = cur->next;
}
cur->next = l1 != NULL ? l1 : l2;
return dum->next;
}Java 代码（@Krahets）：
Java
/**
* 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) {
ListNode dum = new ListNode(0), cur = dum;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
cur.next = list1;
list1 = list1.next;
}
else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
cur.next = list1 != null ? list1 : list2;
return dum.next;
}
}复杂度分析：
- 时间：因为需要遍历
l1、l2两个链表，假设它们的长度为 M, N，那么时间复杂度就是 O(M + N)； - 空间：空间复杂度为 O(1)，仅需要
dum，cur两个常数大小的额外空间。
3. 【方法二】递归法
@腐烂的橘子 + 官方题解
@腐烂的橘子
一、思路
我不看题解完全想不到这个方法，甚至有的题解只要四行就能解决问题（可读性为 0）。不过递归法的时间复杂度仍为 O(M + N)，而空间复杂度也为 O(M + N)，似乎并没有比双指针法更好。
对于本题目：
- 终止条件：两个链表都为空，表示链表已经合并完成；
- 如何递归：我们判断
l1和l2的头节点哪个更小，然后让较小结点的next指向其余结点的合并结果。
写好一个递归就是考虑清楚三个问题：
- 这个问题的子问题是什么（原问题是合并 l1 和 l2，子问题就是【合并
l1.next和l2两个链表，或合并l2->next和l1两个链表】）； - 当前层要干什么事情（选出值较小的头节点，作为合并后链表的头结点，把 next 指向剩余两个链表合并后的结果，即递归调用的返回值，然后将这个结果返回给本层比出的较小头节点）；
- 递归出口（两个链表有一个为空）。
不能习惯地往深处想，不断地想下一层，这样永远想不清楚。
二、代码 & 复杂度分析
C 代码：
C
// 节点定义略
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
// 递归出口
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
// 当前层
if (l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}Java 代码（@腐烂的橘子）：
Java
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}复杂度分析：
- 时间：递归函数每次去掉一个元素，直到两个链表都为空，因此需要调用
R = O(m+n)次。而在递归函数中我们只进行了 next 指针的赋值操作，复杂度为 O(1)，故递归的总时间复杂度为O(T) = R ∗ O(1) = O(m+n)。 - 空间：因为一共调用了 m+n 次，所以使用了 m+n 个栈帧，故空间复杂度为 O(m+n)。