---

🌐 合并两个有序链表 | LeetCode 21 题解

嘿，代码魔术师们！ 👩‍💻👨‍💻 今天我们要闯入链表的奇妙世界，探索如何合并两个有序的链表。这是 LeetCode 的第 21 题：挑战在于把两条有序链表中的元素合并成一个新的有序链表。当然，不让我们开挂，得用原地算法，节省空间！

---

---

🧩 题目概述

🎯 目标

有两个升序的单链表 list1 和 list2，你需要把它们合并为一个升序链表。返回合并后的链表，链表应该是通过拼接 list1 和 list2 节点的方式而成，而不是创建新的节点。

💡 解题思路

1. 特殊情况处理

首先，考虑非常简单的情况：任意一条链表为空。那么，另一条链就是答案。无需多言，直接返回它即可。

2. 一般情况分析

如果两条链表都不为空，我们就需要将它们合并。在这个过程中，我们应该遵循以下步骤：

• 创建一个虚拟头节点 list3。这个节点帮我们轻松地返回合并后的链表。
• 使用一个指针 p，最初指向 list3，用来追踪我们目前遍历/合并到哪个节点了。
• 依次比较两条链表当前节点的值，把较小的那个节点接到合并链表的最后。
• 当到达一条链表的末尾时，直接将另一条链表的剩余部分接到合并链的尾端。

⚙️ 操作步骤

用 C 和 Java 分别实现

C 语言版

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

    // 先考虑特殊情况：有空链
    if (!list1 || !list2) {
        return (list1 == NULL) ? list2 : list1;
    }
    
    struct ListNode list3; // 虚拟头节点
    struct ListNode *p = &list3; // 指针p用于更新list3的节点

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

    p->next = (list1 == NULL) ? list2 : list1;

    return list3.next; // 返回头节点的下一个节点
}

Java 版

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    	// 考虑特殊情况
        if(list1 == null || list2 == null){
            return (list1 == null) ? list2 : list1;
        }

        ListNode list3 = new ListNode(); // 虚拟头节点
        ListNode p = list3; // p 指向 list3
        
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val){
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }

        p.next = (list1 == null) ? list2 : list1;

        return list3.next;
    }
}

🕰️ 复杂度分析

• 时间复杂度：O(n)，n 是两链表中所有节点的个数。每个节点最多被遍历一次。
• 空间复杂度：O(1)，使用的空间仅仅是几个指针，实际数据操作是在原链表上完成的。

🔗 拓展阅读

对于希望深入理解链表及其操作的朋友，我强烈推荐你们探索以下内容：

• 🌟 数据结构：链表的基本操作
• 🌟 递归 vs 迭代：链表问题
• 🌟 链表的魔法：了解双向和循环链表

🤔 实践建议

在编码时，要养成边写边测试的好习惯。尤其是处理链表的时候，检查每一个边缘条件，比如空链表和单节点链表。

🎉 互动环节

• 你在用这段代码时有遇到什么问题吗？
• 有没有比这更简洁的解决方案？欢迎在评论区分享你的见解或对代码的改进！ 🌈

---

感谢阅读！ 希望这篇文章能为你扫清代码迷雾，为你打开新世界的大门！