教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载链表删除是算法面试中的高频考点。本专题基于仓库笔记 2.2 链表-删除.md系统梳理四类删除问题在 O(1) 时间内删除指定结点《剑指 Offer》经典题、只给定结点指针删除该结点、在结点前 O(1) 插入新结点以及删除两个双向循环链表中的相同 data 结点。读完本文你将掌握用后继结点内容覆盖当前结点这一核心技巧的适用边界与完整 C 实现并能独立写出鲁棒的链表删除代码。链表结点定义与前置知识仓库在 2 链表.md 中给出了全系列链表问题的统一结点定义struct ListNode { int m_nKey; ListNode* m_pNext; };本篇删除专题围绕该定义展开。在动手前需要明确两个基本前提单向链表无法回溯删除一个结点必须拿到它的前驱结点否则无法修改前驱的m_pNext指针这正是O(1) 删除技巧存在的意义。鲁棒性要求仓库 剑指offer/README.md 强调代码鲁棒性边界条件、特殊输入、异常处理如空指针删除类题目尤其要处理NULL与待删结点是尾结点两个边界。在 O(1) 时间内删除链表结点题目描述给定链表的头指针和一个结点指针在 O(1) 时间删除该结点。函数声明如下// 链表结点的定义 struct ListNode{ int m_nKey; ListNode* m_pNext; }; // 函数的声明 void deleteNode(ListNode* pListHead, ListNode* pToBeDeleted);为什么不能直接删除常规删除必须找到待删结点的前驱修改前驱的m_pNext指向待删结点的后继。找前驱需要从头遍历最坏情况删除尾结点是 O(n) 时间。O(1) 技巧用下一个结点的内容覆盖当前结点原文档给出的思路非常精炼保存下一个节点的值 tmp删除下一个节点当前节点 tmp即不真正删除 p 本身而是把 p 的后继内容复制进 p再物理删除 p 的后继。这样我们不需要知道 p 的前驱代价仅为 O(1) 的赋值操作。仓库 剑指offer/README.md 中也用同样一句话概括在O(1)时间删除链表节点用下一个节点的内容覆盖当前删除节点的内容删除下一个节点完整 C 实现如下void deleteNode(ListNode* pListHead, ListNode* pToBeDeleted) { if (pListHead NULL || pToBeDeleted NULL) return; // 鲁棒性空指针直接返回 // 情况一待删结点不是尾结点最一般的情况O(1) if (pToBeDeleted-m_pNext ! NULL) { ListNode* pNext pToBeDeleted-m_pNext; pToBeDeleted-m_nKey pNext-m_nKey; // 后继的值覆盖当前结点 pToBeDeleted-m_pNext pNext-m_pNext; // 跳过后继结点 free(pNext); // 物理删除后继结点 } // 情况二待删结点是头结点且链表只有一个结点 else if (pListHead pToBeDeleted) { free(pToBeDeleted); pListHead NULL; // 注意头指针本身无法修改需在调用方将头置空 } // 情况三待删结点是尾结点且链表不止一个结点只能退化为 O(n) 遍历 else { ListNode* pNode pListHead; while (pNode-m_pNext ! pToBeDeleted) pNode pNode-m_pNext; // 找到前驱 pNode-m_pNext NULL; free(pToBeDeleted); } }复杂度与边界分析场景处理方式时间复杂度待删结点有后继值覆盖 删后继O(1)链表仅一个结点也是头结点直接释放O(1)待删结点是尾结点必须遍历找前驱O(n)从平均意义上看只有尾结点这一个特例需要 O(n)整体均摊复杂度为 O(1)。该技巧的适用前提是结点中不保存外部引用、可以被值覆盖——如果结点承载的是无法简单拷贝的复杂对象或外部依赖其地址则不能使用此法这一点在面试中需要主动向面试官说明。只给定结点 p 删除该结点不含尾结点题目描述只给定单链表中某个结点 p并非最后一个结点即p-next ! NULL删除该结点。解题思路原文档描述首先释放 p 中数据然后将p-next的数据 copy 入 p 中接下来删除p-next即可。实现上与上一题情况一完全一致核心代码如下// 前提p 不是尾结点p-m_pNext ! NULL void deleteNodeOnly(ListNode* p) { ListNode* pNext p-m_pNext; p-m_nKey pNext-m_nKey; // 后继数据 copy 入 p p-m_pNext pNext-m_pNext; // 绕过后继 free(pNext); // 删除后继结点 }注意题目明确限定p 并非最后一个结点因为当 p 是尾结点时没有后继可用来覆盖此时若不给定头指针则无解——这也是与上一题的区别所在上一题给了头指针可以遍历找前驱。变式在结点 p 前 O(1) 插入一个结点原文档同时给出对称问题只给定单链表中某个结点 p非空结点在 p 前面插入一个结点。思路先分配一个新结点 q将 q 插入在 p 之后再把 p 中的数据 copy 入 q最后将待插入的数据记录到 p 中。整个过程不访问前驱仍是 O(1) 复杂度。void insertBeforeNode(ListNode* p, int value) { ListNode* q (ListNode*)malloc(sizeof(ListNode)); if (q NULL) return; // 分配失败保护 // 1. q 先插到 p 的后面 q-m_pNext p-m_pNext; p-m_pNext q; // 2. 把 p 的旧数据搬到 q实现逻辑上 q 在 p 之前 q-m_nKey p-m_nKey; // 3. 新数据写进 p p-m_nKey value; }插入后链表顺序为原 p 前驱 → p存放新值→ q存放 p 的旧值→ 原 p 后继从数据序列角度看等价于在 p 前插入了value。这一个技巧与值覆盖删除互为镜像面试时常配套考察。删除两链表中 data 值相同的结点双向循环链表题目描述有两个双向循环链表 A、B结点定义为struct node{ int data; struct node *front,*next; };已知头指针为pHeadA、pHeadB请写一函数将两链表中 data 值相同的结点删除。问题拆解双向循环链表front指向前驱next指向后继且头尾相连的特点是任意结点都有前驱指针删除任意结点都能在 O(1) 内完成指针重连无需像单链表那样遍历找前驱。删除一个双向循环链表结点p的核心操作p-front-next p-next; p-next-front p-front; free(p);因此本题的难点不在删除本身而在如何高效地判断两个链表中的 data 是否相同。方案一哈希表记录 A 的 data 集合推荐遍历链表 A把每个结点的data值放入哈希表Set重复值只需记录一次遍历链表 B对每个结点查询哈希表若命中则将该结点从 B 中摘除利用双向链表 O(1) 重连若题目要求两边的相同结点都删则还需反向再处理一次 A以 B 的 data 集合为参照遍历 A 删除命中结点。时间复杂度 O(|A| |B|)空间复杂度 O(|A|)。哈希表方案在仓库其他专题如 HashMap in Java.md中亦有充分讨论是以空间换时间的典型应用。方案二双重循环暴力删除无额外空间对 A 的每个结点遍历 B 查找相同 data。找到后需要维护当前结点指针的连续性——因为删除当前结点后原指针已失效必须先用临时变量保存后继再删除struct node* p pHeadA; do { struct node* q pHeadB; do { if (p-data q-data) { struct node* pNext p-next; // 先保存后继 p-front-next p-next; p-next-front p-front; free(p); p pNext; // 继续检查下一结点 break; // 本题只要求删除重复结点 } q q-next; } while (q ! pHeadB); // 循环链表的终止条件 if (p NULL) break; // 防御防止删空 } while (p ! pHeadA);时间复杂度 O(|A| × |B|)空间复杂度 O(1)。注意循环链表遍历用do...while且终止条件为回到头结点删除后指针失效的问题必须通过先存后继再删规避。边界条件清单空链表pHeadA NULL || pHeadB NULL直接返回单结点链表删除后链表为空头指针需置NULL函数内改不了调用方指针需通过返回新头或二级指针解决删除全部结点防止出现对已释放结点的二次访问data 相同但在各自链表中出现多次需明确题意是删一个还是全删。总结链表删除题型的解题框架将本专题四类问题归纳为一张速查表题目变体给定条件核心技巧复杂度O(1) 删除指定结点头指针 结点指针后继值覆盖当前结点O(1) 均摊只给定结点 p 删除结点 p非尾同上O(1)在 p 前插入结点结点 p非空先插后继再搬数据O(1)双向循环链表去重两个头指针哈希表判重 双向 O(1) 摘除O(n m) 时间核心规律一句话单链表无法 O(1) 拿到前驱就用后继覆盖绕开前驱能拿到前驱双向链表就直接重连指针。完整代码示例与更多链表题型排序、双链表相交、合并可继续阅读仓库的 2 链表.md、2.1 链表-排序.md 与 2.3 链表-2条.md并对照 剑指offer/README.md 中链表一节的面试题清单进行系统训练。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐PyTorch-CycleGAN损失函数详解Cycle Consistency如何保证转换质量PyTorch CycleGAN损失函数详解Cycle Consistency如何保证转换质量 CycleGAN是一种强大的无监督图像转换模型它能够在没有Learn-Algorithms 字符串删除专题双指针原地删除与 O(N) 算法解析Learn Algorithms 字符串删除专题双指针原地删除与 O N 算法解析 字符串删除是算法面试中的高频基础题难点不在于“删掉一个字符”而在于 在教程CS-Notes 剑指 Offer 题解在 O(1) 时间内删除链表节点的原理与实现CS Notes 剑指 Offer 题解在 O 1 时间内删除链表节点的原理与实现 本篇基于 CS Notes https://link.gitcode.co知识库文档教程上一篇微信聊天记录导出WeChatMsg 完整指南三种格式永久保存下一篇lax.js企业级应用大型项目中的实施策略创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考