LeetCode 21: 合并两个有序链表

🏷️ 链表 | 递归 | Dummy节点

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

---

🤔 解题思路

在做这道题目的时候，我希望能不开辟新的内存来存储结果，而是直接使用现有的链表的其中之一。但是当我实际在写代码的时候发现这会带来非常多的临界条件需要额外进行判断。

就在这时，我突然想到可以建一个 dummy 节点，这样就能完美的规避额外的条件判断！

💡 Dummy节点的妙用

Dummy节点（哨兵节点）是链表题目中的常用技巧，它可以：

• 统一头节点和其他节点的处理逻辑
• 避免对空链表的特殊判断
• 简化代码结构，减少边界条件

📝 代码实现

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy;
    struct ListNode* tail = &dummy; // tail 就够了，不需要 res, head, cur...

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

    // 一行解决所有剩余问题
    tail->next = list1 != NULL ? list1 : list2;

    return dummy.next;
}

---

✨ 收获与总结

这道题虽然简单，但却让我真正掌握和理解了 dummy 节点的巧妙之处。通过一个简单的哨兵节点，代码变得更加简洁优雅，这种技巧在后续的链表题目中会经常用到！

复杂度分析

• 时间复杂度: O(m + n)，其中 m 和 n 分别是两个链表的长度
• 空间复杂度: O(1)，只使用常数个指针变量