【刷题第十天】21. 合并两个有序链表

一、题目描述：

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

示例 1：

输入： l1 = [1,2,4], l2 = [1,3,4]输出： [1,1,2,3,4,4]复制代码

二、思路分析：

这个题目也是计算机数据结构与算法的基础题目，如果没记错，我应该也做过，但这次我还是没能成功写出递归法，只会迭代。

迭代法

迭代法思想非常简单:首先我们维护一个 prehead 指针，作为合并后链表的头指针，另外维护一个 prev 指针，新加入的元素添加到这里，然后更新 prev 的 next 字段。

具体流程是这样的，假设两个待合并链表为 l1 和 l2，l1 和 l2 指针目前分别指向头元素

• 两个列表都是有序的，因此我们 l1 和 l2 所指头元素的大小将较小的元素添加到 prev 上 prev 后移，较小的元素指针后移

• 重复上述流程，直至 l1 或者 l2 其中之一遍历到终点

• 当遍历终止时，l1 和 l2 至多有一个是非空的。由于两个链表都是有序的，那么意味着此时的非空部分它包含的元素一定大于前面合并过的元素，因此直接将此非空链表连接到 合并链表之后就行。

递归法

递归法真是人类难题。哦不，是我的难题!

我阅读了题解的解释，我发现我是个蠢猪，就是个猪。这么简单的递归我都想不出来，我人麻了。

递归就是分情况，我们递归的定义两个链表中的 merge 操作:

• 当 l1[0] < l2[0] 时，l1[0] + merge(l1[1:],l2)

• 当 l1[0] > l2[0] 时，l2[0] + merge(l1,l2[1:])

也就是说头部值较小的顶点与剩余部分元素 merge

临界条件:我们要考虑递归的边界条件:

• l1 和 l2 都为空链表，没有任何操作需要合并

• l1 和 l2 有个为空，递归结束

三、AC 代码：

var mergeTwoLists = function(l1, l2) {    if (l1 === null) {        return l2;    } else if (l2 === null) {        return l1;    } else if (l1.val < l2.val) {        l1.next = mergeTwoLists(l1.next, l2);        return l1;    } else {        l2.next = mergeTwoLists(l1, l2.next);        return l2;    }};复制代码

四、总结：

递归算法如此简单，但我还是写不出来，难受啊。希望后面可以好好总结总结递归，找出递归的大致流程。