LeetCode 21：合并两个有序链表

题目描述

题目链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

题目与思路分析

目标分析：

1. 将两个升序链表合并为一个升序链表
2. 返回新链表的头指针
3. 新链表中的结点由已有两链表中的节点组成
4. 提高要求：时间复杂度为 O(n)，空间复杂度为 O(1)

思路一：尾插

思路：创建一个新的空链表 newHead，同时逐个遍历两个链表的结点，将 val 较小的节点尾插到新链表中。

操作：

• 注意对空链表的处理，两个链表可能都为空，也可能任意一个为空。
• 遍历：循环继续的条件为 curNode1 && curNode2，只要有一个链表结束，结束即可，将未遍历完的链表直接整体尾插到新链表中。
  • curNode1 和 curNode2：分别用于遍历链表一和链表二
  • tailNode：尾结点，方便尾插时找尾
• curNode1->val <= curNode2->val 时，说明：curNode1 需要被尾插到新链表。
  • 第一次尾插时 (if(newHead == nullptr) 需要特殊处理：
    • tailNode = newHead = curNode;
    • curNode = curNode->next;
  • 其余结点的尾插，常规化处理：
    • tailNode->next = curNode;
    • tailNode = tailNode->next;
  • 插入完后：curNode = curNode->next;
• curNode1->val > curNode2->val 时和上面是一样的逻辑。
• 循环结束后，检查哪个链表未遍历完全，直接整体尾插到新链表中。

// 循环结束后，可能链表还有剩余元素
if(curNode1) tailNode->next = curNode1;
if(curNode2) tailNode->next = curNode2;

思路二：哨兵位优化

思路：使用带哨兵位的头结点优化尾插，在带哨兵位的链表中进行尾插时，无需特殊处理第一次尾插时的情况。

操作：

• 注意对空链表的处理，两个链表可能都为空，也可能任意一个为空。
• 遍历：循环继续的条件为 curNode1 && curNode2，只要有一个链表结束，结束即可，将未遍历完的链表直接整体尾插到新链表中。
  • curNode1 和 curNode2：分别用于遍历链表一和链表二
  • tailNode：尾结点，方便尾插时找尾
• curNode1->val <= curNode2->val 时，说明：curNode1 需要被尾插到新链表。
  • 有了哨兵位的头结点，结点的尾插，都能常规化处理：
    • tailNode->next = curNode;
    • tailNode = tailNode->next;
  • 插入完后：curNode = curNode->next;
• curNode1->val > curNode2->val 时和上面是一样的逻辑。
• 循环结束后，检查哪个链表未遍历完全，直接整体尾插到新链表中。
• 保存新链表的头结点：ListNode* newHead = guardNode->next，为 guardNode 的 next 结点。
  • 释放 guardNode，防止内存泄露。
• 最终返回新的头结点 return newHead;

guardNode->next = nullptr;
delete guardNode;

代码实现

思路一

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 空链表判断
        if (list1 == nullptr && list2 == nullptr)
            return nullptr;
        if (list1 == nullptr || list2 == nullptr) {
            if (list1) return list1;
            if (list2) return list2;
        }
        // 以下 两个链表都不为空
        ListNode* curNode1 = list1;
        ListNode* curNode2 = list2;
        ListNode* newHead = nullptr, *tailNode = nullptr;
        while (curNode1 && curNode2) {
            // 更小的元素尾插到新结点
            if (curNode1->val <= curNode2->val) {
                // 第一个节点直接尾插
                if (newHead == nullptr) {
                    newHead = tailNode = curNode1;
                }
                // 其他节点直接 尾插
                else {
                    tailNode->next = curNode1;
                    tailNode = tailNode->next;
                }
                curNode1 = curNode1->next;
            } else {
                // 第一个节点直接尾插
                if (newHead == nullptr) {
                    newHead = curNode2;
                    tailNode = curNode2;
                }
                // 其他节点直接 尾插
                else {
                    tailNode->next = curNode2;
                    tailNode = tailNode->next;
                }
                curNode2 = curNode2->next;
            }
        }
        // 循环结束后，可能链表还有剩余元素
        if (curNode1) tailNode->next = curNode1;
        if (curNode2) tailNode->next = curNode2;
        return newHead;
    }
};

思路二

// 使用带哨兵位的头结点 优化算法
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        
        ListNode* curNode1 = list1, *curNode2 = list2;
        // 遍历链表，用于迭代
        // 尾插需要找尾，提前保存，避免重复找
        ListNode* guardNode = new ListNode();
        ListNode* tailNode = guardNode;
        
        while (curNode1 && curNode2) {
            // 将小的那个结点，尾插到 guardNode 后面
            if (curNode1->val <= curNode2->val) {
                tailNode->next = curNode1;
                tailNode = tailNode->next;
                curNode1 = curNode1->next;
            } else {
                tailNode->next = curNode2;
                tailNode = tailNode->next;
                curNode2 = curNode2->next;
            }
        }
        // 有一个链表结束后，将另一个链表再链接上
        if (curNode1) tailNode->next = curNode1;
        if (curNode2) tailNode->next = curNode2;
        
        // 保存新的头结点，并释放内存，防止内存泄露
        ListNode* newHead = guardNode->next;
        guardNode->next = nullptr;
        delete guardNode;
        
        // 返回新结点
        return newHead;
    }
};

算法代码优化

优化思路一

• 优化了空链表返回的逻辑
• 其中一个链表为空，就返回另一个链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        
        // 以下 两个链表都不为空
        ListNode* curNode1 = list1;
        ListNode* curNode2 = list2;
        ListNode* newHead = nullptr, *tailNode = nullptr;
        while (curNode1 && curNode2) {
            // 更小的元素尾插到新结点
            if (curNode1->val <= curNode2->val) {
                // 第一个节点直接尾插
                if (newHead == nullptr) {
                    newHead = tailNode = curNode1;
                }
                // 其他节点直接 尾插
                else {
                    tailNode->next = curNode1;
                    tailNode = tailNode->next;
                }
                curNode1 = curNode1->next;
            } else {
                // 第一个节点直接尾插
                if (newHead == nullptr) {
                    newHead = curNode2;
                    tailNode = curNode2;
                }
                // 其他节点直接 尾插
                else {
                    tailNode->next = curNode2;
                    tailNode = tailNode->next;
                }
                curNode2 = curNode2->next;
            }
        }
        // 循环结束后，可能链表还有剩余元素
        if (curNode1) tailNode->next = curNode1;
        if (curNode2) tailNode->next = curNode2;
        return newHead;
    }
};

优化思路二

• 优化了初始链表判空的处理
• 这里无需对空链表进行处理：通过分析得知
  • 当 list1 或 list2 为 nullptr 时，不会进入 while 循环。由于 guardNode 非空， ListNode* newHead = guardNode->next，因此保存的 newHead 时一定合法。
  • 当 list1 或 list2 全为 nullptr 时，newHead 即为 nullptr
  • 当 list1 或 list2 其中一个为 nullptr 时，newHead 即另一个链表的头结点

// 使用带哨兵位的头结点 优化算法
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 遍历链表的结点
        ListNode* curNode1 = list1, *curNode2 = list2;
        // 尾插需要找尾，提前保存，避免重复找
        ListNode* guardNode = new ListNode();
        ListNode* tailNode = guardNode;
        
        while (curNode1 && curNode2) {
            // 将小的那个结点，尾插到 guardNode 后面
            if (curNode1->val <= curNode2->val) {
                tailNode->next = curNode1;
                tailNode = tailNode->next;
                curNode1 = curNode1->next;
            } else {
                tailNode->next = curNode2;
                tailNode = tailNode->next;
                curNode2 = curNode2->next;
            }
        }
        // 有一个链表结束后，将另一个链表再链接上
        if (curNode1) tailNode->next = curNode1;
        if (curNode2) tailNode->next = curNode2;
        
        // 保存新的头结点，并释放内存，防止内存泄露
        ListNode* newHead = guardNode->next;
        guardNode->next = nullptr;
        delete guardNode;
        
        // 返回新结点
        return newHead;
    }
};