东营市河口区建设局网站,深圳网站建设 设计贝尔利,男女做羞羞的事情网站,网站开发软件成本题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入#xff1a;l1 [1,2,4], l2 [1,3,4]
输出#xff1a;[1,1,2,3,4,4]思路
每次递归都会比较当前两个节点的值#xff0c;选择较小的节点作为合并后的链…题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例
输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]思路
每次递归都会比较当前两个节点的值选择较小的节点作为合并后的链表的下一个节点并继续递归合并剩余部分。(等于情况谁都可以这里判给(list2) 这个过程会持续进行直到有一个链表为空然后将另一个链表直接连接到合并后的链表的末尾。因为是非递减的链表所以可以这样直接合并。
测试代码
class Solution{public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1null)return list2;if (list2null)return list1;if (list1.vallist2.val){list1.nextmergeTwoLists(list1.next, list2);return list1;}else {list2.nextmergeTwoLists(list1, list2.next);return list2;}}
}
复杂度
时间复杂度 最坏情况下每次递归都会处理一个节点并且每个节点都需要比较和连接操作。 假设 n 是 list1 的长度m 是 list2 的长度。 所以总体时间复杂度为 O(n m)。 空间复杂度 在最坏情况下递归深度达到 n m。 因此空间复杂度为 O(n m)线性级别。
测试结果
