【LeetCode_21】合并两个有序链表

刷爆LeetCode系列

• LeetCode第21题：
• github地址
• 前言
• 题目描述
• 题目与思路分析
  • 思路一：尾插
  • 思路二
• 代码实现
  • 思路一
  • 思路二
• 算法代码优化
  • 优化思路一
  • 优化思路二

LeetCode第21题：

github地址

有梦想的电信狗

前言

• 本文用C++解答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：尾结点，方便尾插时找尾
• curNode->val <= curNode2->val时，说明：curNode1需要被尾插到新链表
  • 第一次尾插时(if(newHead == nullptr)需要特殊处理：
    • tailNode = newHead = curNode;
    • curNode = curNode->next;
  • 其余结点的尾插，常规化处理：
    • tailNode->next = curNode;
    • tailNode = tailNode->next;
  • 插入完后：curNode = curNode->next;
• curNode->val > curNode2->val时和上面是一样的逻辑
• 循环结束后，检查哪个链表未遍历完全，直接整体尾插到新链表中
• 最终返回return newHead;

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

思路二

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

操作：

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

 guardNode->next =nullptr;delete guardNode 

代码实现

思路一

classSolution{public: ListNode*mergeTwoLists(ListNode* list1, ListNode* list2){// 空链表判断if(list1 ==nullptr&& list2 ==nullptr)returnnullptr;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;}};

思路二

// 使用带哨兵位的头结点 优化算法classSolution{public: ListNode*mergeTwoLists(ListNode* list1, ListNode* list2){if(list1 ==nullptr)return list2;if(list2 ==nullptr)return list1; ListNode* curNode1 = list1,*curNode2 = list2;// 遍历链表，用于迭代// 尾插需要找尾，提前保存，避免重复找 ListNode* guardNode =newListNode(); 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;}};

算法代码优化

优化思路一

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

classSolution{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即另一个链表的头结点

// 使用带哨兵位的头结点 优化算法classSolution{public: ListNode*mergeTwoLists(ListNode* list1, ListNode* list2){// 遍历链表的结点 ListNode* curNode1 = list1,*curNode2 = list2;// 尾插需要找尾，提前保存，避免重复找 ListNode* guardNode =newListNode(); 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;}};

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！你的每一次互动，都是对作者最大的鼓励！征程尚未结束，让我们在广阔的世界里继续前行！ 🚀