做网站第一步要干啥,网站建设广告平台推广,泰安网络教育,广东省建设厅官方网站系列目录
88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 …系列目录
88.合并两个有序数组 52.螺旋数组 567.字符串的排列 643.子数组最大平均数 150.逆波兰表达式 61.旋转链表 160.相交链表 83.删除排序链表中的重复元素 389.找不同 1491.去掉最低工资和最高工资后的工资平均值 896.单调序列 206.反转链表 92.反转链表II 141.环形链表 142.环型链表 目录 系列目录21. 合并两个有序列表24. 两两交换链表中的节点内存泄漏 (Memory Leak ) ⚠️小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 )
内存泄漏是指程序在申请内存后未能正确地释放它导致系统内存的浪费甚至在运行时占用越来越多的内存使程序崩溃甚至可能导致系统可用内存耗尽而变得不稳定
对于任何动态内存分配的问题处理好内存泄漏是非常必要的
为了避免内存泄漏可以采取以下措施
确保每个new都有对应的delete每当使用new来创建一个节点时都应该确保在适当的时候使用delete来释放它 这通常发生在节点不再需要时例如在删除节点或链表被销毁时使用智能指针C11及以后的版本引入了智能指针 (如unique_ptr、shared_ptr )它们可以自动管理内存并在适当的时候释放它 使用智能指针可以大大简化内存管理并减少内存泄漏的风险避免野指针野指针是指已经被释放但仍然被引用的指针 如果试图通过野指针访问内存或释放已经释放的内存都会导致不可预测的行为包括内存泄漏 因此应该确保在释放内存后立即将指针设置为nullptr以避免野指针的问题使用RAII (Resource Acquisition Is Initialization )原则RAII是一种编程技术它要求将资源的生命周期与对象的生命周期绑定在一起 通过这种方法可以确保在对象不再需要时自动释放其占用的资源包括内存进行内存泄漏检测使用工具 (如Valgrind、AddressSanitizer等 )来检测内存泄漏 这些工具可以帮助你发现潜在的内存泄漏问题并提供有关如何修复它们的建议
