21. 合并两个有序链表

一、题目

二、思路和题解

1.思路

思路较为直观，直接按题目要求逐步处理。先考虑特殊情况：如果其中一个链表为空，则返回另一个链表（两个链表都为空的情况也包含在内）。

一般情况准备两个指针分别指向两个链表的头节点，每一步比较大小，将较小的值放入新创建的节点中，然后该链表的指针后移。循环终止条件为其中一个链表的节点遍历完毕。由于输入链表均为非降序排列，此时将另一个链表剩余部分拼接到合并链表末尾即可。

2.代码

/**
 * Definition for singly-linked list.
 * 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:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 特殊情况：当至少一个链表是空，直接返回另一条链表
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;

        // 定义两个指针方便取数比大小
        ListNode* ptr1 = list1;
        ListNode* ptr2 = list2;

        // 新链表的第一个节点
        ListNode* res = new ListNode();
        ListNode* head = res; // 头指针

        // 先比较第一个节点的数，谁小就谁放在新的节点里
        if (ptr1->val <= ptr2->val) {
            res->val = ptr1->val;
            ptr1 = ptr1->next;
        } else {
            res->val = ptr2->val;
            ptr2 = ptr2->next;
        }

        // 当某一个链表遍历完了就结束循环
        while (ptr1 != nullptr && ptr2 != nullptr) {
            ListNode* newnode = new ListNode();
            res->next = newnode;
            if (ptr1->val <= ptr2->val) {
                newnode->val = ptr1->val;
                ptr1 = ptr1->next;
            } else {
                newnode->val = ptr2->val;
                ptr2 = ptr2->next;
            }
            res = res->next;
        }

        // 判断一下到底是哪条链表已经遍历完了，便于选择另一条链表接着拼
        if (ptr1 == nullptr) {
            while (ptr2 != nullptr) {
                ListNode* newnode = new ListNode();
                res->next = newnode;
                newnode->val = ptr2->val;
                res = res->next;
                ptr2 = ptr2->next;
            }
        } else {
            while (ptr1 != nullptr) {
                ListNode* newnode = new ListNode();
                res->next = newnode;
                newnode->val = ptr1->val;
                res = res->next;
                ptr1 = ptr1->next;
            }
        }
        return head;
    }
};

三、其他解法

1.迭代

和上面的思路类似，但不需要新开辟空间建链表，只需要改变指针指向把两个链表合并在一起。

算法： 首先设定一个哨兵节点 prehead，方便最后返回合并后的链表。然后用 prev 指针来拼接两个链表，调整它的 next 指针。重复以下过程，直到 l1 或者 l2 指向 null：如果 l1 当前节点的值小于等于 l2，就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位；否则对 l2 做同样的操作。不管接哪一个元素，都需要把 prev 向后移一位。

在循环终止的时候，l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。

代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);
        ListNode* prev = preHead;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = (l1 == nullptr) ? l2 : l1;
        return preHead->next;
    }
};

2.递归

可以把这个合并的过程定义为递归式：

• 若 list1[0] < list2[0]，则 list1[0] + merge(list1[1:], list2)
• 否则 list2[0] + merge(list1, list2[1:])

算法： 如果 l1 或者 l2 一开始就是空链表，那么没有任何操作需要合并，直接返回非空链表。否则，判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束（边界条件）。

代码：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 边界条件
        if (l1 == nullptr) return l2;
        else if (l2 == nullptr) 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;
        }
    }
};

四、错误回顾

用 new 创建链表节点并插入时注意语法正确性：

ListNode *newnode = new ListNode(val);
cur->next = newnode;
cur = cur->next;

常见错误包括构造函数参数遗漏或类型拼写错误。