【LeetCode_21. 合并两个有序链表】

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路一：（迭代）

新建一个哑结点，循环把两个链表表头元素最小的那个链接到哑结点后面；

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    void printList(ListNode* li) {
        ListNode* li_cp = li;
        while (li_cp != nullptr) {
            cout << (li_cp->val) << " ";
            li_cp = li_cp->next;
        }
        cout << "END" << endl;
    }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //创建哑结点
        ListNode temp = ListNode(0);
        ListNode* pre = &temp;//新链表的工作指针
        //如果两个都不为空
        while (list1 && list2) {
            //先把list1和list2中小的元素放到新链表中
            if (list1->val < list2->val) {
                pre->next = list1;
                list1 = list1->next;
            }
            else {
                pre->next = list2;
                list2 = list2->next;
            }
            pre = pre->next;
        }
        // 合并后 list1 和 list2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        pre->next = (list1 == NULL ? list2 : list1);
        return temp.next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

思路二：（递归）

链表合并递归问题的子问题：

• 当两个链表一个为空，一个不空，肯定是把不空的那个链接到结果链表上；
• 当两个链表都不空，肯定是把元素值小的那个链接到结果链表上，然后再递归地合并；
• 如果list1的值<=list2的值，以list1当前值作为头，继续合并list1的next与list2，写成代码就是list1->next=合并（list1->next,list2）
• 如果list2的值<list1的值，以list2当前值作为头，继续合并list2的next与list1，写成代码就是list2->next=合并（list2->next,list1）

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    void printList(ListNode* li) {
        ListNode* li_cp = li;
        while (li_cp != nullptr) {
            cout << (li_cp->val) << " ";
            li_cp = li_cp->next;
        }
        cout << "END" << endl;
    }
    ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2) {
        //如果list1空了，就返回list2
        if (list1 == NULL) return list2;
        //如果list2空了，就返回list1
        if (list2 == NULL) return list1;

        //如果list1，list2都不空
        //如果list1的值小于list2的值，那么就以list1的值为头，继续合并list1的下一个和list2
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;        //返回list1
        }
        //如果list2的值小于list1的值，那么就以list2的值为头，继续合并list2的下一个和list1
        else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;         //返回list2
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

参考于此大佬的解题思路： traveller-lzx