算法学习：递归

21. 合并两个有序链表

背景：链表

目的：合并两个升序链表

方法：递归

在之前的学习中我们了解到了“自底向上”和”自顶向下”两种递归方式，也意识到两种递归生成的栈的构造不同，对于这到题，可能需要程序栈的理解。

对于 A 和 B 两个结点，如果 A > B 的话，我们希望合并之后的结果是 B -> next = A ，这个过程会产生两个结果：

1. B 作为两个结果中的较小值保留在该次递归调用生成的栈中
2. B 作为已经合并之后的头节点，其地址要返回给上层调用

那么 A 应该是什么？

A 是 上一轮递归结束之后返回的较小的结点，如果你能理解“自顶向下”的递归相当于从两个链表的尾部开始合并的话，那么，每次完成的操作即是：两个链表中次大和最大的结点合并，返回合并后的头结点，然后再将两链表中剩余的次大和最大结点合并，返回合并后的头结点…

于是在递归生成的程序栈中，自动为这些结点排好了序，通过返回的头结点相连结。

所以在递归的过程中，如果确定了谁最小，那么就在较大的结点和下一个结点中找到较小的进行合并。

还需要确定的是递归的出口条件：

在合并的过程中，一定会出现一个链表先于另一个链表结束遍历的情况，此时说明另一个链表中剩余的部分均大于或等于已经遍历结束的链表，于是仅需要将剩余部分的头结点返回即可。

最终的代码如下：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
        {
            return l2;
        }
        else if(!l2)
        {
            return l1;
        }
        else if(l1->val >= l2->val)
        {
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
        else
        {
            l1->next = mergeTwoLists(l1->next,l2);
            return l1;
        }
    }
};