题目：

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

思路：

• 终止条件：当 list1 或 list2 为空时，直接返回另一个链表的头节点。这样如果其中一个链表为空，函数会立即返回另一个链表。

• 比较当前节点值：递归地比较 list1 和 list2 当前节点的值，选择较小的节点作为当前合并链表的头部，并让它的 next 指针指向合并后的子链表。

  • 如果 list1->val < list2->val，则 list1 作为新链表的头部，并递归合并 list1->next 和 list2。
  • 否则，list2 作为新链表的头部，并递归合并 list1 和 list2->next。

• 返回合并后的链表头：每次递归调用返回较小节点，并继续连接剩余部分，最终构建完整的合并链表。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL){
        return list2;
    }
    if(list2 == NULL){
        return list1;
    }
    if(list1 -> val < list2 -> val){
        list1 -> next = mergeTwoLists(list1 -> next, list2);
        return list1;
    }else{
        list2 -> next = mergeTwoLists(list1, list2 -> next);
        return list2;
    }
}

设计递归算法的三要素：

1. 明确结束的条件
2. 明确终止时采取的办法
3. 提取需要重复进行的部分