题目要求

• 示例 1：
  输入：l1 = [1,2,4], l2 = [1,3,4]
  输出：[1,1,2,3,4,4]
• 示例 2：
  输入：l1 = [], l2 = []
  输出：[]
• 示例 3：
  输入：l1 = [], l2 = [0]
  输出：[0]

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

解法

链表顺序枚举

按顺序对两链表的当前node进行数值的比对，符合条件者入新链表，并找该node的next继续进行这个比对操作，直到其中一个链表到头。此时将未遍历完的链接合到已有链上即可。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* preHead = new ListNode(-1);
        ListNode* curr = preHead;


        while (list1 != nullptr && list2 != nullptr)
        {
            if (list1->val <= list2->val)
            {
                curr->next = list1;
                list1 = list1->next;
            }
            else 
            {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }

        curr-> next = list1 == nullptr ? list2:list1;
        
        return preHead->next;
    }
};

复杂度分析
时间复杂度：遍历两链表$O(n+m)$
空间复杂度：$O(1)$

递归解法

递归的理解是，求两个链表的合并，即是每个节点后接上该节点的后续链和另外一条链的合并。递归终止条件是其中一条链为空，此时返回另外一条链。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
        {
            return list2;
        }
        else if (list2 == nullptr)
        {
            return list1;
        }
        
        if (list1->val <= list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else 
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

复杂度分析
时间复杂度：遍历两链表$O(n+m)$
空间复杂度： $O(min(n,m))$到$O(n+m)$，需要用到函数堆栈，容量与两链表的长度相关，最小函数堆栈为两个链表中较短的那一条的大小，最大即需要一直将所有节点都遍历一遍，此时函数堆栈大小为n+m。