LeetCode：经典题之21、24 题解及延伸

系列目录

88.合并两个有序数组
52.螺旋数组
567.字符串的排列
643.子数组最大平均数
150.逆波兰表达式
61.旋转链表
160.相交链表
83.删除排序链表中的重复元素
389.找不同
1491.去掉最低工资和最高工资后的工资平均值
896.单调序列
206.反转链表
92.反转链表II
141.环形链表
142.环型链表

---

---

⚠️小tips

一般处理链表问题

相比迭代，递归算法更容易想到，但空间复杂度更高

而迭代仅需常数级的空间复杂度≈O(1)，但有时会有些费脑子

21. 合并两个有序列表

🌟链表+递归+迭代

原题链接

C++
若未特殊标明，以下题解均写用C++

方法一 递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/// 宏定义没有 ;分号
#define list1 l1
#define list2 l2class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (l1 == nullptr) return l2;else if (l2 == nullptr)return l1;else if (l1->val <= l2->val) {// 比较 l1->next 和 刚刚参与比较的 l2l1->next = mergeTwoLists(l1->next, l2);// 还要继续利用原 l1找到l1.next，所以后返回 l1return l1;} else {// 同理l2->next = mergeTwoLists(l2->next, l1);return l2;}}
};

方法二 迭代

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/// 注意顺序不要反了，原名在前# define list1 l1# define list2 l2
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 定义一个哨兵💂 快速返回合并后的链表// 不妨定义值为 -1 ListNode* dummyHead = new ListNode(-1);// 维护(preserve)一个 prev指针，让其移动ListNode* prev = dummyHead;while (l1 != nullptr && l2 != nullptr) {if (l1->val <= l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}// 调整 prev的位置prev = prev->next;}// l1 或 l2 定会有一个先指向空// 三元条件运算符prev->next = l1 == nullptr ? l2 : l1;return dummyHead->next;}
};

有关三元条件运算符 和 哨兵(哑节点/虚拟头节点)可以参考这篇文章

24. 两两交换链表中的节点

🌟链表+递归+迭代
原题链接

C++
若未特殊标明，以下题解均写用C++

方法一 递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {// 相邻节点两两交换，原链表第2个节点即新链表的第1个节点// 而newHead->next 又恰为除去这两个节点的链表的头节点// 且swapParis() 的变量是链表的 头节点// 故可以递归地完成两两交换// 如果链表长度为 0或1，无法交换——不如说无需交换if (head == nullptr || head->next == nullptr)return head;ListNode *newHead = head->next;head->next = swapPairs(newHead->next);newHead->next = head;// newHead 为交换后链表的头节点return newHead;}
};

方法二 迭代

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {// new一个 虚拟头节点ListNode* dummy = new ListNode(0);dummy->next = head;// 定义临时(temporary)节点 temp，记录尚未处理好的链表的头节点ListNode* temp = dummy;while (temp->next != nullptr && temp->next->next != nullptr) {// 定义 node1(节点1) 和 node2ListNode* node1 = temp->next;ListNode* node2 = temp->next->next;temp->next = node2;node1->next = node2->next;// 用完再更新 node2node2->next = node1;// 记得更新 temp// 指针跟着节点走的temp = node1;}// 记得删除这个 dummyListNode *res = dummy->next;delete dummy;return res;}
};

内存泄漏 (Memory Leak )：

内存泄漏是指程序在申请内存后，未能正确地释放它，导致系统内存的浪费，甚至在运行时占用越来越多的内存，使程序崩溃甚至可能导致系统可用内存耗尽而变得不稳定

对于任何动态内存分配的问题，处理好内存泄漏是非常必要的

为了避免内存泄漏，可以采取以下措施：

1. 确保每个new都有对应的delete：每当使用new来创建一个节点时，都应该确保在适当的时候使用delete来释放它 这通常发生在节点不再需要时，例如在删除节点或链表被销毁时
2. 使用智能指针：C++11及以后的版本引入了智能指针 (如unique_ptr、shared_ptr )，它们可以自动管理内存，并在适当的时候释放它 使用智能指针可以大大简化内存管理，并减少内存泄漏的风险
3. 避免野指针：野指针是指已经被释放但仍然被引用的指针 如果试图通过野指针访问内存或释放已经释放的内存，都会导致不可预测的行为，包括内存泄漏 因此，应该确保在释放内存后立即将指针设置为nullptr，以避免野指针的问题
4. 使用RAII (Resource Acquisition Is Initialization )原则：RAII是一种编程技术，它要求将资源的生命周期与对象的生命周期绑定在一起 通过这种方法，可以确保在对象不再需要时自动释放其占用的资源，包括内存
5. 进行内存泄漏检测：使用工具 (如Valgrind、AddressSanitizer等 )来检测内存泄漏 这些工具可以帮助你发现潜在的内存泄漏问题，并提供有关如何修复它们的建议