- 难度: 简单
- 考察: 链表
- 来源: https://leetcode-cn.com/problems/merge-two-sorted-lists/
- 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0021-Merge-Two-Sorted-Lists/Article/0021-Merge-Two-Sorted-Lists.md
- 题解: https://github.com/azl397985856/leetcode/blob/master/problems/21.MergeTwoSortedLists.md
题目
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
1 | 输入:1->2->4, 1->3->4 |
思路
常规方法
- 两个链表其中一个为空时返回另一个链接作为结果;
- 记录head和current头;
- 两个链表取小值往后遍历。
递归法
- 两个链表其中一个为空时返回另一个链接作为结果;
- 头部较小的一个与剩下的元素合并,并返回排好序的链表头。
关键点
- 链表结构
- 边界
复杂度
- 时间复杂度:O(M+N)
- 空间复杂度:O(M+N)
代码
常规方法
1 | /** |
递归法
1 | /** |