本文主要是介绍Leetcode NO.21 Merge Two Sorted Lists 合并链表(有序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Leetcode NO.21 Merge Two Sorted Lists && 合并链表(有序)
文章目录
- Leetcode NO.21 Merge Two Sorted Lists && 合并链表(有序)
- 1.问题描述
- 2.测试用例
- 示例 1:
- 示例 2:
- 示例 3:
- 3.提示
- 4.代码
- 1.迭代
- code
- 复杂度
- 2.递归
- code
- 复杂度
1.问题描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
2.测试用例
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
3.提示
- 两个链表的节点数目范围是
[0, 50]
-100 <= Node.val <= 100
l1
和l2
均按 非递减顺序 排列
4.代码
1.迭代
code
public ListNode mergeTwoListsWithLoop(ListNode l1, ListNode l2) {ListNode sentinel = new ListNode();ListNode pre = sentinel;while (l1 != null && l2 != null) {if (l1.val < l2.val) {pre.next = l1;pre = l1;l1 = l1.next;} else {pre.next = l2;pre = l2;l2 = l2.next;}}pre.next = l1 == null ? l2 : l1;return sentinel.next;
}
复杂度
* 时间复杂度 O(m + n) m、n 分别为链表的长度
* 空间复杂度 O(1)
2.递归
code
public ListNode mergeTwoListsWithRecursion(ListNode l1, ListNode l2) {//1.定义结束条件if (l1 == null) {return l2;}if (l2 == null) {return l1;}//2. 逻辑递归if (l1.val < l2.val) {l1.next = mergeTwoListsWithRecursion(l1.next, l2);return l1;} else {l2.next = mergeTwoListsWithRecursion(l1, l2.next);return l2;}
}
复杂度
* 时间复杂度 O(m + n) m、n 分别为链表的长度
* 空间复杂度 O(m + n ) m、n 分别为链表的长度
这篇关于Leetcode NO.21 Merge Two Sorted Lists 合并链表(有序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!