- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
说起递归，大家可以看下我之前整理的这篇文章，你真的懂递归吗？
题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4思路
1.使用递归来解题
2.将两个链表头部较小的一个与剩下的元素合并
3.当两条链表中的一条为空时终止递归
关键点
- 掌握链表数据结构
- 考虑边界情况
复杂度分析
n+m是两条链表的长度
- 时间复杂度：O(m+n)
- 空间复杂度：O(m+n)
constmergeTwoLists=function(l1,l2){if(l1===null){returnl2}if(l2===null){returnl1}if(l1.val<l2.val){l1.next=mergeTwoLists(l1.next,l2)returnl1}else{l2.next=mergeTwoLists(l1,l2.next)returnl2}}