C++ 链表算法学习笔记（学习+刷题）

前言链表是算法入门的最大难点绝大多数新手报错、做题出错基本都是因为分不清指针和节点、看不懂链表结构、不会处理边界情况。本篇笔记用通俗直白的语言梳理链表必备知识点、刷题模板和常见坑适合新手快速吃透、直接拿来刷题复用。一、核心基础彻底分清「节点」和「指针」1. 简单理解定义链表节点 ListNode真正存数据的“车厢”里面有数值 val 和指向下一节车厢的 next是链表的真实内容。节点指针 ListNode*记录车厢位置的“地址标签”只负责找节点本身不存任何数据不是链表的一部分。2. 访问节点的固定规则访问节点数据只有两种写法死记即可实实在在的节点不带*用.访问例dummy.val指针/地址标签带*用-访问例head-val、cur-next3. 最容易混淆的两个操作指针移动cur cur-next只是把“标签”挪到下一个节点链表本身没变。修改链表结构cur-next xxx修改了车厢的连接关系会断链、改链真正改变链表。严禁操作空指针nullptr是空标签没有指向任何节点强行访问next会直接程序报错。二、头指针 head 通俗理解1. 定义head 就是链表的头部地址标签永远指向链表第一个有效数据节点它只是一个指针本身不是链表节点。2. 核心特性cur head临时指针 cur 复制了 head 的地址两个标签指向同一条链表操作的是同一组节点。遍历链表时只移动 curhead 固定不动防止找不到链表开头。刷题返回结果要么返回原头指针 head要么返回虚拟头节点的后继dummy.next。三、刷题神器虚拟头节点1. 作用链表最麻烦的就是删除/修改第一个节点需要单独判断边界。dummy 是一个空的“傀儡节点”放在链表最前面不存有效数据能让所有节点的操作逻辑完全一致不用单独处理头节点大幅减少bug。2. 通用模板ListNode dummy; // 创建虚拟头节点 dummy.next head; // 将虚拟头节点连接到原链表头部 ListNode* cur dummy; // 使用指针 cur 从虚拟头节点开始遍历 // 在此处进行链表的增、删、改、查等操作 return dummy.next; // 返回新链表的头节点即原链表的头部四、链表三大核心刷题操作1. 链表遍历核心原则用临时指针遍历坚决不动 head保证链表头部不丢失。ListNode* cur head; while(cur ! nullptr){ // 对当前节点做操作 cur cur-next; }2. 删除节点高频考点核心口诀删节点必找前驱不能直接删掉目标节点想要删除某个节点必须找到它前一个节点让前一个节点直接连上后一个节点跳过目标节点。示例A-B-C删除 B写法A-next A-next-next删除倒数第N个节点通用规则len 链表总节点数不用 dummy需要往前走len - n - 1步找到前驱节点边界特殊情况len n要删的是第一个节点直接返回head-next3. 链表截取链表没有数组那样的切片功能截取片段只需要两步1. 找到想要的起始节点、末尾节点2. 把末尾节点的 next 置空断链。重点返回某个中间节点时会默认带上它后面所有节点输出后半段完整链表不会只返回单个值。五、经典算法模板1. 快慢指针规则慢指针一次走1步快指针一次走2步。适用场景找链表中点、判断链表有没有环、一趟遍历删除倒数第n个节点。逻辑简单、效率极高是链表刷题核心算法。2. 迭代反转链表用 pre、cur、nxt 三个指针配合先保存下一个节点再反转当前节点的指向最后依次后移指针循环完成整条链表反转无递归开销稳定性最强。六、配套知识点C整数除法规则C整数除法一律向0取整不是单纯的向下取整正数直接舍去小数7 / 3 2负数向0靠拢-7 / 3 -2和向下取整不同正整数向上取整通用公式(a b - 1) / b七、高频易错点符号用错实体节点用.指针必须用-gt;空指针报错对空的 nullptr 访问 next程序直接崩溃删点错误直接操作目标节点没有找前驱节点删错数据概念混淆误以为移动指针会改变链表结构边界遗漏忘记单独处理删除头节点的特殊情况认知误区不知道返回节点会自带后续整条链表八、总结遍历只用临时指针头指针不动保全局删点必先找前驱dummy 规避头节点边界指针移动不改链赋值重连才改结构快慢指针搞定中点、判环、倒数节点截取链表只需断尾返回节点自带后缀。