21. 合并两个有序链表
难度简单1687收藏分享切换为英文接收动态反馈
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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
均按 非递减顺序 排列
- Merge Two Sorted Lists
Easy
6624765Add to ListShare
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]
. -100 <= Node.val <= 100
- Both
l1
andl2
are sorted in non-decreasing order.
使用递归实现,新链表也不需要构造新节点
- 终止条件:两条链表分别名为
l1
和l2
,当l1
为空或l2
为空时结束 - 返回值:每一层调用都返回小的链表头,然后返回节点的next节点继续参与递归
class Solution {
public ListNode mergeTwoLists(ListNode l1, 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;
}
}
}