Leetcode 21 合并两个有序链表

异步根系
• 阅读 1107

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

解题思路

从链表头开始比较,l1l2 是有序递增的,所以比较 l1.vall2.val 的较小值就是合并后链表的最小值,次小值就是小节点的 next.val 与大节点的 val 比较的较小值,依次递归,直到递归到 l1l2 均为 null

当递归到任意链表为 null ,直接将 next 指向另外的链表即可,不需要继续递归了。

代码实现

function mergeTwoLists(l1, l2) {
  if (l1 == null) return l2;
  if (l2 == null) return l1;

  if (l1.val <= l2.val) {
    // 如果 l1.val <= l2.val ,次小值就是 l1.next 与 l2 比较的较小值
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    // 如果 l1.val > l2.val ,次小值就是 l2.next 与 l1 比较的较小值
    l2.next = mergeTwoLists(l2.next, l1);
    return l2;
  }
};
点赞
收藏
评论区
推荐文章
待兔 待兔
11个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
275,环形链表 II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。如果 pos 是 1,则在该链表中没有环。说明:不允许修改给定的链表。示例1:输入:head3,2,0,4,pos
Wesley13 Wesley13
3年前
JAVA实现双向链表的增删功能
JAVA实现双向链表的增删功能,完整代码  1.packagelinked;3.classLinkedTable{5.}6.publicclassLinkedTableTest{8.  //构造单链表9.  staticNodenode1newNode("name1");10.
Stella981 Stella981
3年前
Linux下V4L2捕捉画面+H264压缩视频+帧缓冲显示视频————结合三个部分工作
前面三篇文章分别介绍了视频捕获、h264视频压缩、帧缓冲显示的实现,现在将他们结合起来摄像头采集到的数据,需要交给视频压缩线程、显示线程使用,那么我采用的方法是使用队列及链表来实现:1.摄像头采集到数据后,分别放入两个处理线程队列中,并将相关信息放入链表中2.两个线程处理完成数据后,调用回调函数,从链表里找到对应的节点,然后释
Wesley13 Wesley13
3年前
Java源码解析之LinkedList源码剖析(基于JDK1.8)
    学过数据结构的都知道双端队列(链表),没学过的也没有关系,下面我先介绍一下双端队列(链表),为什么要介绍它了,因为LinkedList本质上就是一个双端队列(链表)。一. 双端队列(链表)的介绍1. 如下图:双端队列(链表)中单个节点对应的结构!(https://oscimg.oschina.net/oscn
Stella981 Stella981
3年前
LeetCode 92. 反转链表 II(Reverse Linked List II)
题目描述反转从位置_m_到_n_的链表。请使用一趟扫描完成反转。说明:1≤ _m_ ≤ _n_ ≤链表长度。示例:输入:12345NULL,m2,n4输出:14325NULL解题思路本题类似于反转链表
Stella981 Stella981
3年前
LeetCode 142 环形链表 II python
题目描述给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回null。说明:不允许修改给定的链表。样例如果不是环,则输出None如果是环,则输出入口节点想法:通过ac141,知道慢节点循环的次数就是环的长度无环的情况不用考虑,直接返回No
Stella981 Stella981
3年前
C#Redis列表List
转载自:https://www.cnblogs.com/5ishare/p/6291034.html一、前戏 在Redis中,List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表一样,我们可以在其头部(left)和尾部(right)添加新的元素。在插入时,如果该键并不存在,Redis将为该键创建一个新的链表。与此相反,如果链表中所有的元
Wesley13 Wesley13
3年前
83. 删除排序链表中的重复元素
题目描述题目地址:https://leetcodecn.com/problems/removeduplicatesfromsortedlist/给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。示例1:输入:112输出:12示例 2:输入:11233输出:
菜园前端 菜园前端
2年前
什么是链表?
原文链接:什么是链表?链表是有序的数据结构,链表中的每个部分称为节点。可以首、尾、中间进行数据存取,链表的元素在内存中不必是连续的空间,每个节点通过next指针指向下一个节点。优点链表的添加和删除不会导致其余元素位移。缺点无法根据索引快速定位元素。数组和链
异步根系
异步根系
Lv1
为了赞美而去修行,有如被践踏的香花美草。
文章
4
粉丝
0
获赞
0