1. 题目

1.1 英文题目

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

1.2 中文题目

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

1.3输入输出

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

1.4 约束条件

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

2. 分析

2.1 非递归算法

代码如下：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head_node(0);
        ListNode* cur_node = &head_node;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur_node->next = l1;
                l1 = l1->next;
            } else {
                cur_node->next = l2;
                l2 = l2->next;
            }
            cur_node = cur_node->next;
        }
        cur_node->next = (l1 != nullptr ? l1 : l2);
        return head_node.next;
    }
};

参考：https://leetcode.com/problems/merge-two-sorted-lists/discuss/9714/14-line-clean-C%2B%2B-Solution

2.2 递归算法

代码如下：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr || (l2 != nullptr && l1->val > l2->val) ) {//为了让当前的l1始终小于l2
            swap(l1, l2);
        }
        if (l1 != nullptr) {
            l1->next = mergeTwoLists(l1->next, l2);//将小的节点依次加入l1
        }
        return l1;
    }
};

参考：https://leetcode.com/problems/merge-two-sorted-lists/discuss/9814/3-lines-C%2B%2B-(12ms)-and-C-(4ms)