21. 合并两个有序链表

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

一道简单题，如果有迭代的方法实在太简单了，不过多论述了。
相反，用递归可能思考起来没那么简单了。
用递归首先

• 1:终止条件，如果l1,l2是空的，那么可以直接返回另外一个链表。
• 2:每次递归进行的操作是什么
  无非就是判断当前两个链表的值哪个小，小的不用动，那么就将其余的节点连接到这个节点上就可以了。
  请注意，第一次即判断两个链表的第一个值哪个更小，更小的那个作为返回值返回。如果l1的第一个值比l2的第一个值小，那么就返回l1，并将排序好的都接到l1后面，反之亦然。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* 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;
        }
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。