题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
难度:Middle
前置知识
公司
- 阿里
- 字节
- 腾讯
- amazon
- apple
- microsoft
公司
- 阿里、字节、腾讯
思路
本题可以使用递归来解,将两个链表头部较小的一个与剩下的元素合并,并返回排好序的链表头,当两条链表中的一条为空时终止递归。
关键点
- 掌握链表数据结构
- 考虑边界情况
代码
- 语言支持:JS
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:前端中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
复杂度分析
M、N 是两条链表 l1、l2 的长度
- 时间复杂度:$O(M+N)$
- 空间复杂度:$O(M+N)$
扩展
- 你可是使用迭代的方式求解么?
- 原题leetcode链接:21.merge-two-sorted-lists
更多题解可以访问我的 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com