LeetCode 之 JavaScript 解答第21题 —— 合并两个有序链表（Merge Two

wdzgege 发布于2019-08-23 16:51 / 1069人阅读

摘要：什么意思呢比如上方合并链表的代码，分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。

Time：2019/4/9
Title: Merge Two Sorted Lists
Difficulty: Easy
Author: 小鹿

题目：Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solve:

▉ 算法思路

1、正常思路，循环遍历迭代比较大小，每取出一个数据，将小数据加入到额外的数组中去，直到比较完毕，将其中一个剩余的数组追加到额外的数组尾部。

2、递归思路，满足递归的三个条件：

将问题能不能化为子问题去解决？

子问题的解决方式是否和总问题相似？

是否有终止条件？

▉ 递归实现

var mergeTwoLists = function(l1, l2) {
    let result = null;
    //终止条件
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    //判断数值大小递归
    if(l1.val < l2.val){
        result = l1;
        result.next = mergeTwoLists(l1.next,l2);
    }else{
        result = l2;
        result.next = mergeTwoLists(l2.next,l1);
    }

    //返回结果
    return result;
};

▉ 怎么理解递归？

其实递归最难的就是我们应该怎么去理解它，当我们完全理解了递归之后，就会发现递归非常方便，代码简洁。

我们经常理解递归会陷入到递归的细节上去，往往只递，归的时候就完全模糊了，我也试着找了网上的关于递归解释的，这么说吧，关于递归理解和使用，只有总结出自己的一套理解方法，才能真正的掌握递归，下面总结一下我自己理解的递归。

1、明确递归可以解决什么问题，也就是上边所讲到的解决的问题应该满足递归的三个条件。详细分开讲解：

将问题划分为子问题：如果我们判断该问题可以用递归解决了，比如合并两个链表中比较结点大小，然后加入到新链表，然后在比较下一个结点大小，这个过程就是一个将问题化为子问题的过程，比较当前结点大小先要比较后一个节点与当前结点的大小，可以理解成“递”的过程。（就好比一扇扇包含关系的大门，问一共有几所大门，你拿着要是去打开，发现里边还有一扇，然后再打开，发现还有一扇，直到最后一扇。通常我们使用迭代循环来解决这个问题，就好比打开一扇大门就加一；而递归要做的就是当大门全部打开的时候，从里往外走关闭大门的时候统计大门的数量）

寻找终止条件：递归必须有个终止条件，也就是子问题的解决方案，如果没有终止条件，问题就不会得到解答。如上方合并链表的时候，经过递归不断的比较下一结点，知道其中一个链表比较完毕为空了，结果返回第二个链表，也就是达到了终止的条件，开始“归”的过程。

递推公式：你会问了，怎么写出递推公式呢？既然终止条件有了，那我们开始找出递归公式，下面是我自己总结出来的经验。

① 一看参数和 return。什么意思呢？比如上方合并链表的代码，分别明确函数的参数和返回值是什么？参数是两个合并的链表结点头结点。返回值是合并后的链表。

② 二凑参数和return。就是说我们要去按照参数和返回值去用递归伪造它，比较完成第一个结点，当然传入第二个节点，返回第一个结点到新链表尾部，那么递归就会返回新链表的下一结点。要屏蔽掉递归的细节，只看参数和返回值。

▉ 递归缺点

有时候问题可以使用递归，但是由于递归的缺点会放弃使用。

1、递归警惕堆栈溢出。

2、警惕递归重复元素计算。

3、递归的高空间复杂度。

▉ 怎么正确写出递归代码？

1、将问题化为子问题。

2、解决子问题。

3、寻找终止条件。

4、写出递归公式。

5、将递推公式转化为代码。

欢迎一起加入到 LeetCode 开源 Github 仓库，可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡，共同完善我们的开源小仓库！
Github：https://github.com/luxiangqia...

GPU云服务器云服务器合并链表的c语言两个日期之差合并两个单链表 21天学javascript

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103412.html

LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿题目：Merge K...

zhou_you 2019-08-23 16:53 评论0 收藏0
LeetCode 21：合并两个有序链表 Merge Two Sorted Lists

摘要：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。无非是依次将两个链表每个节点的值对比，取出值较小的节点，添加到新链表末尾。将剩余链表传回递归函数。将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 Merge two sorted linked lists and return it as a n...

LeviDing 2019-07-31 11:31 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
leetcode21 Merge Two Sorted Lists 将两个有序链表组合成一个新的有

摘要：题目要求翻译过来就是将两个有序的链表组合成一个新的有序的链表思路一循环在当前两个链表的节点都是非空的情况下比较大小，较小的添入结果链表中并且获得较小节点的下一个节点。题目要求 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing togeth...

BothEyes1993 2019-08-14 18:05 评论0 收藏0