Skip to main content

合并两个有序链表

· 5 min read
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——21题​

💡 参考代码：​

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/**
 * 合并两个升序链表为一个新的升序链表
 * 
 * @param list1 第一个升序链表的头节点
 * @param list2 第二个升序链表的头节点
 * @return 返回合并后的新升序链表的头节点
 * 
 * 时间复杂度: O(m + n)，其中m和n分别是两个链表的长度
 * 空间复杂度: O(1)，只使用了常数级别的额外空间
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 创建一个虚拟头节点，简化边界处理
    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    
    // 初始化虚拟头节点
    dummy.next = NULL;
    
    // 当两个链表都未遍历完时，比较节点值并连接较小的节点
    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;
    }
    
    // 连接剩余的节点（其中一个链表可能还有剩余节点）
    if (list1 != NULL) {
        tail->next = list1;
    } else {
        tail->next = list2;
    }
    
    // 返回合并后链表的真正头节点
    return dummy.next;
}

📖 总结：​

点击展开题目总结

🤔 合并两个有序链表

1️⃣ 题目核心信息​

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

📥 输入输出：

  • 输入：
    • list1: 第一个升序链表的头节点
    • list2: 第二个升序链表的头节点
  • 输出：返回合并后的新升序链表的头节点

2️⃣ 实现原理​

💡 核心思路：使用双指针法依次比较两个链表当前节点的值，将较小的节点连接到结果链表中，直到其中一个链表遍历完，再将另一个链表的剩余部分连接到结果链表。

📋 实现步骤：

  1. 创建虚拟头节点简化操作
  2. 使用双指针遍历两个链表
  3. 比较当前节点值，将较小的节点连接到结果链表
  4. 移动对应链表指针和结果链表指针
  5. 处理剩余未遍历完的链表节点

3️⃣ 关键点解析​

给出原始做题思路并比较与最优解区别（可选）

🎯 代码技巧​

  • 使用虚拟头节点(dummy node)简化链表操作
  • 双指针技术遍历两个有序链表
  • 利用链表的有序性优化合并过程

4️⃣ 使用场景​

✅ 适用情况：​

  • 合并两个有序数据集
  • 归并排序算法中的合并步骤
  • 链表相关算法题的基础操作

⚠️ 前提条件：​

  • 两个链表均为升序排列
  • 链表节点结构一致

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(m + n)，其中 m 和 n 分别是两个链表的长度，需要遍历两个链表的所有节点

  • 💾 空间复杂度：O(1)，只使用了常数级别的额外空间，没有使用额外的数据结构

6️⃣ 注意事项​

🚩 边界情况：​

  • 其中一个或两个链表为空
  • 两个链表长度不同
  • 链表中存在相同值的节点

💥 易错点：​

  • 忘记处理剩余未遍历完的链表节点
  • 没有正确维护结果链表的尾指针
  • 对空链表的处理不当

7️⃣ 补充说明​

让我们通过一个具体例子来逐步演示 mergeTwoLists 函数的执行过程：

假设有两个升序链表：

  • list1: 1 -> 2 -> 4
  • list2: 1 -> 3 -> 4

📌 初始状态：​

list1: 1 -> 2 -> 4 -> NULL
       ↑
     list1指针

list2: 1 -> 3 -> 4 -> NULL
       ↑
     list2指针

dummy: [ ]
       ↑
      tail指针

🔁 第1次循环：​

比较 list1->val(1) 和 list2->val(1)，由于 1 <= 1，选择 list1 的节点:

list1: 1 -> 2 -> 4 -> NULL
            ↑
          list1指针

list2: 1 -> 3 -> 4 -> NULL
       ↑
     list2指针

dummy: [ ] -> 1
       ↑      ↑
     tail   (原list1节点)

🔁 第2次循环：​

比较 list1->val(2) 和 list2->val(1)，由于 2 > 1，选择 list2 的节点：

list1: 1 -> 2 -> 4 -> NULL
            ↑
          list1指针

list2: 1 -> 3 -> 4 -> NULL
            ↑
          list2指针

dummy: [ ] -> 1 -> 1
       ↑           ↑
     tail    (原list2节点)

🔁 第3次循环：​

比较 list1->val(2) 和 list2->val(3)，由于 2 <= 3，选择 list1 的节点：

list1: 1 -> 2 -> 4 -> NULL
                 ↑
               list1指针

list2: 1 -> 3 -> 4 -> NULL
            ↑
          list2指针

dummy: [ ] -> 1 -> 1 -> 2
       ↑                ↑
     tail         (原list1节点)

🔁 第4次循环：​

比较 list1->val(4) 和 list2->val(3)，由于 4 > 3，选择 list2 的节点：

list1: 1 -> 2 -> 4 -> NULL
                 ↑
               list1指针

list2: 1 -> 3 -> 4 -> NULL
                 ↑
               list2指针

dummy: [ ] -> 1 -> 1 -> 2 -> 3
       ↑                     ↑
     tail              (原list2节点)

🔁 第5次循环：​

比较 list1->val(4) 和 list2->val(4)，由于 4 <= 4，选择 list1 的节点：

list1: 1 -> 2 -> 4 -> NULL
                      ↑
                   list1指针(已为NULL)

list2: 1 -> 3 -> 4 -> NULL
                 ↑
               list2指针

dummy: [ ] -> 1 -> 1 -> 2 -> 3 -> 4
       ↑                          ↑
     tail                   (原list1节点)

🏁 循环结束处理：​

此时 list1 已为 NULL，将 list2 的剩余部分连接到结果链表：

list2: 1 -> 3 -> 4 -> NULL
                      ↑
                   list2指针(已为NULL)

dummy: [ ] -> 1 -> 1 -> 2 -> 3 -> 4 -> 4
       ↑                               ↑
     tail                        (原list2节点)

✅ 最终结果：​

返回 dummy.next，即得到合并后的链表：1 -> 1 -> 2 -> 3 -> 4 -> 4

加载评论中...