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：https://github.com/luxiangqiang/JS-LeetCode
网友评论