leetcode 21. 合并两个有序链表 js实现
2023-09-14 09:07:43 时间
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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
均按 非递减顺序 排列
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ // 迭代 // 时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m) // 空间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。 var mergeTwoLists = function(list1, list2) { if(!list1){ return list2 } if(!list2){ return list1 } // 定义一个空的链表 let res = new ListNode(-1); // 复制该链表,因为迭代过程中会改变链表 let ans = res; // 迭代结束条件为当一个链表遍历结束即停止 while(list1&&list2){ // 当list1节点大,则先指向list2 节点 if(list1.val>=list2.val){ res.next = list2; // 同时改变 list2 指针为下一个继续对比 list2 = list2.next; }else{ res.next = list1; list1 = list1.next; } // 每次迭代,改变当前链表的指向,以进行正确指向 res = res.next; } // 最后迭代结束后,可能会有一个链表还有剩余,且由于是递增的,所以直接等于剩余的链表头节点即可 res.next = list1?list1:list2; // 返回空节点的下一个即为最终的结果 return ans.next; }; // 递归 // 空间复杂度:O(1)。我们只需要常数的空间存放若干变量 // 时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)。 var mergeTwoLists = function(list1, list2) { // 递归结束条件,当一个链表为null时,直接返回另一个 if(!list1){ return list2 } if(!list2){ return list1 } // 如果 list1 链表当前节点值小于 list2.val if(list1.val<=list2.val){ // 则将 list1的下一个指向 list2,list2 的下一个指向 list1.next list1.next = mergeTwoLists(list2,list1.next); // 最终返回 list1 return list1; }else{ // 如果 list2 链表当前节点值小于 list1.val // 则将 list2的下一个指向 list1,list1 的下一个指向 list2.next list2.next = mergeTwoLists(list1,list2.next); // 最终返回 list2 return list2; } };
相关文章
- leetcode 1019. 链表中的下一个更大节点 js实现
- leetcode 191 二进制中1的个数 js 实现
- 设计循环队列(leetcode 622)
- Leetcode 通过率最高的困难题 N皇后 II 【回溯解法-剪枝】
- ☆打卡算法☆LeetCode 188. 轮转数组 算法解析
- leetcode-2两数相加[通俗易懂]
- leetcode 647. 回文子串 js实现
- Leetcode 题目927-三等分0和1组成的数组
- leetcode刷题(132)——完全背包问题思路理解
- JavaScript刷LeetCode-字符串类解题技巧
- leetcode 32. 最长有效括号 js实现
- leetcode 206. 反转链表 js实现
- leetcode 234. 回文链表 js 实现
- LeetCode 第3题 无重复字符的最长子串(小白详解)
- JS获取当前年份_js获取当前时间年月日
- JavaScript刷LeetCode拿offer-js版字典
- 【day10】LeetCode(力扣)刷题(注释详细)[707.设计链表][278.第一个错误的版本][98. 验证二叉搜索树]
- leetcode 1351. 统计有序矩阵中的负数 js实现
- leetcode 54. 螺旋矩阵 js高效实现
- Js刷LeetCode拿offer-并查集
- Js刷LeetCode拿offer-双指针技巧(下)
- LeetCode - #69 x 的平方根
- JavaScript刷LeetCode拿offer-js版字典
- JavaScript刷LeetCode拿offer-树的遍历
- LeetCode 82:删除排序链表中的重复元素 II
- 原生 JS 实现 HTML 转 Markdown ,html2md.js
- LeetCode 设计循环队列(C语言)
- clipboard.js:最轻便的复制页面内容到剪切板的JS
- JS技术连接Oracle数据库实现数据交互(js连接oracle实例)
- JS函数验证总结(方便js客户端输入验证)
- js获取url参数代码实例分享(JS操作URL)