★ FEATURED ARTICLE 1. 从数组“跳到”链表为什么说链表是动态结构的起点数组和链表就像排队买奶茶的两种方式数组是固定座位的电影院座位号连续、容量开票时定死链表则是游乐园的“贪吃蛇车队”每一节车厢只知道自己拉的下一节是谁想加长就随时在队尾挂一节不需要整队人挪位置。我在“代码随想录”系列刷到链表这一天最大的感受是**之前用数组写代码形成的思维惯性在这里会反复被纠正。**数组的随机访问是O(1)链表的随机访问是O(n)数组的插入删除要搬动后续元素链表只需要改两个指针。这两个“反向思维”如果没转过弯来后面的题全部会写得十分别扭。这篇博客我打算围绕三件事展开链表的基本结构、构造方式以及节点定义在C和Python里分别怎么写几个高频操作删除倒数第N个节点、反转链表、合并有序链表从思路到代码的完整推导刷链表题最容易踩的坑指针乱了、空指针访问、虚拟头节点没用对以及如何通过画图和“三步走”方法稳定规避。适合的读者是刚刚结束数组练习、准备进入链表章节的初学者或者刷题时经常写着写着就“链子断了”的朋友。这里不要求你有多高深的算法基础只要会写基本的循环和递归就能顺着文章把代码复现出来。2. 链表的基础设施节点定义、虚拟头节点与遍历边界2.1 节点定义数据结构里最朴素的“一个盒子装一个指针”链表的最小单位是节点。一个节点内部至少要装两样东西当前节点保存的值以及指向下一个节点的引用。C里常用struct来定义Python则用一个class即可。// C定义单链表节点 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) {} };# Python定义单链表节点 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next理论上任何可以装“数据 下一个节点地址”的容器都能当节点用但用class或struct去定义是为了让结构更清晰也更贴合力扣、牛客这类平台里的接口要求。实际面试写题时大多数时候我们并不需要自己创建链表题目会直接给一个头节点但笔试里偶尔也会要求手动构造链表这种定义方式就要背熟。这里想多说一句为什么C用指针、Python用“引用”C的指针就是变量地址ListNode *next存的是另一个节点在内存里的位置Python里的next其实也是一个对象引用本质是“知道那个节点在哪”。二者虽然语法不同但在链表的指针操作逻辑上完全一致所以刷题时用自己在C里养成的指针思路去写Python几乎可以无缝移植。2.2 虚拟头节点一个被很多人忽略的“统一处理”技巧链表最烦的操作往往是“改头”。比如删除头节点和删除中间某个节点逻辑其实是两种。删除中间节点只要让前一个节点跳过它pre-next cur-next但删除头节点时根本没有“前一个节点”你得单独写一个head head-next。这会让代码多很多if判断。解决办法是构建一个虚拟头节点也叫dummy node让它指向真正的头dummy-next head。这样一来链表的每个节点都拥有了“前驱”对头节点的操作和对中间节点的操作就能用同一套代码不用做任何特判。以删除第N个节点为例我习惯这样建虚拟头ListNode* dummy new ListNode(0, head);在Python里则是dummy ListNode(0, head)也许有人会问既然返回值依然是dummy-next那这个dummy节点本身存储的0值有什么意义它只是为了占位让头节点也有前驱。删除完成之后返回dummy-next即可即便原来的头节点被删了新的头节点也可以通过它重新拿到。2.3 遍历边界while(head ! nullptr) 和 while(head-next ! nullptr) 的差异新手最容易写混的地方是遍历条件。很多链表题写着写着就越界本质是在想“我到底要访问当前节点还是访问当前节点的下一个”这个问题上没理清楚。如果你要“访问每一个节点的值”条件是while (cur ! nullptr)这样可以保证cur最终走到nullptr时停止期间每个节点的val都能访问到。如果你要“判断当前节点的下一个是否存在”条件是while (cur-next ! nullptr)这通常用于“找倒数第二个节点”“找中间节点的前一个节点”这类需求。还有一个高频操作快慢指针法找链表中间节点。此时快指针每次跳两步慢指针每次跳一步判断条件通常写成while (fast ! nullptr fast-next ! nullptr)。这个复合条件一定不能忘掉fast-next ! nullptr否则fast跳两步时可能一步就跳到空指针上然后访问fast-next-next直接崩溃。我自己的习惯是写代码之前先用手在链表图上走一遍明确每一步指针落在哪个节点上再决定循环条件写成什么。这个习惯帮我节省了无数debug时间。3. 三个高频操作完整推演删除、反转、合并3.1 删除倒数第N个节点一次遍历 快慢指针力扣第19题“删除链表的倒数第N个结点”是最典型的“一次遍历就能完成删除”的题目。很多人第一反应是先遍历一遍数出链表长度再走到“正数第长度-N个节点”处删除。这样当然能做但需要两次遍历。快慢指针法可以做到只遍历一遍。思路是让快指针先走N步然后快慢指针一起走。等快指针走到末尾时慢指针恰好停在“要删除节点的前一个节点”上。为什么停在前一个因为删除必须知道前驱。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0, head); ListNode* fast head; ListNode* slow dummy; // fast先走 n 步 while (n--) { fast fast-next; } // 快慢指针一起走 while (fast ! nullptr) { fast fast-next; slow slow-next; } // 现在 slow 是待删除节点的前一个 slow-next slow-next-next; return dummy-next; }这个解法里最巧妙的设计是让慢指针初始化为dummy理由正是2.2节说的删除头节点时也需要有一个“前驱”。当N等于链表长度时快指针走完N步正好变成nullptr接着进入第二个循环时条件不成立慢指针停留在dummy随后slow-next slow-next-next删除的其实是原来的头节点。整个过程完全没有特判。我给自己的做题口诀是快先走N快慢一起走快没了慢就在目标前一个。画图时快指针是探路人慢指针是收割者二者保持N个节点的距离这个距离本身就是“倒数第N”的定义。3.2 反转链表迭代法里“三根指针各司其职”反转链表大概是面试出现频率最高的链表题。迭代法的核心是三个指针prev、cur、nextTemp。prev表示已经反转好的部分的前一个节点cur表示当前正在处理的节点nextTemp临时保存cur原本的下一个节点避免反转后链表断掉。代码如下ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nextTemp cur-next; // 1. 暂存下一个节点 cur-next prev; // 2. 反转当前节点 prev cur; // 3. prev移动到当前 cur nextTemp; // 4. cur移动到原下一个 } return prev; }这四步每一步都不能省顺序也不能乱。我见过不少同学写反转链表时先把cur-next prev写了再去保存nextTemp结果原来的后继丢了整个链表断成两截。我自己的做法是把它当一个固定流程背下来但更重要的是理解每一步在干什么先保存“后路”不然反转完当前节点就找不到后面了把当前节点的指针倒过来prev推进到当前节点cur沿着后路继续走。可以想象成一群人手拉手排队你让每个人转身但转身之前必须先记住自己身后是谁否则转身之后整个队伍就散了。这个类比每次写代码时在我脑子里过一遍基本不会出错。3.3 合并两个有序链表递归写法是最短路径合并有序链表的经典要求是给定两个升序链表把它们合并成一个新的升序链表。两种主流写法里递归在可读性上明显优于迭代。递归的思路一句话每次比较两个链表的头节点谁小就选谁并在它后面接上“剩余部分合并的结果”。def mergeTwoLists(list1, list2): if not list1: return list2 if not list2: return list1 if list1.val list2.val: list1.next mergeTwoLists(list1.next, list2) return list1 else: list2.next mergeTwoLists(list1, list2.next) return list2理解递归的关键是信任函数的定义mergeTwoLists()本身就是一个已经能用的函数它会返回合并后的头节点。我们只需要处理当前最小的这一步递归剩下的交给函数自己。我也遇到过很多人问递归为什么不会栈溢出像合并这样O(n)的递归深度只有当链表特别长时才值得担心日常刷题完全没问题。面试时如果面试官要求迭代实现也可以顺手把递归改成迭代——迭代写法本质上是用一个dummy节点作为结果链表的尾巴不断把较小节点挂上去最后把剩余链表整体接上。4. 从“会写”到“写得稳”画图法、统一操作和边界清单4.1 画图是链表题唯一靠谱的debug方式我强烈建议在纸上或者白板上画出链表操作的每一步尤其是在写代码之前。链表题全部围绕指针操作展开而指针操作在脑海里模拟三四个节点之后就很容易乱套。画图不需要多精美方块表示节点箭头表示next指向就行关键是每画一步就更新一次指针状态。例如反转链表画成三行第一行是初始状态prev在前cur在头nextTemp在cur-next第二行是第一步暂存第三行是完成反转后的关系。每次代码报错回到图里按箭头走一遍就能定位是哪一步写反了。我自己的刷题环境里经常同时开着两个窗口左边是代码编辑器右边是简笔画。也许有人觉得麻烦但根据我的经验图上的推理比脑子里空想来得快得多尤其是涉及“倒数第N个节点”“环形链表入口”这类绕来绕去的题目画图就是最高效的引导。4.2 虚拟头节点 统一删除逻辑删除节点是链表里最典型的一类操作。如果不使用虚拟头节点删除头节点和删除中间节点的代码逻辑完全不同得叠加一层条件判断使用虚拟头节点之后统一删除逻辑就变成// 删除 cur 节点 prev-next cur-next;整个过程不再区分“头”和“中间”。所以我在每一道删除类题目的代码里都默认带上dummy哪怕有特殊需求不需要它写上去也只增加一行代码而省下的是大量特判。对于“删除所有重复节点”这类题目比如一个有序链表里有重复值要求把重复节点全都去掉只保留没有重复出现的元素虚拟头节点的必要性会更强。因为一旦头节点本身是重复值它也要被删除没有dummy做前驱就只能写得非常憋屈。4.3 边界条件清单写链表代码前花十秒过一遍链表题的bug几乎都出在边界。每次提交之前我会在脑子快速过下面这张清单场景需要检查的问题空链表head是否为nullptr循环条件是否直接跳过单节点链表反转后返回的是否仍是那个节点删除后是否返回nullptr双节点链表删除倒数第1个时快指针走完N步的状态是否正确删除头节点dormant节点的前驱逻辑是否覆盖尾节点删除slow-next-next是否为非法访问这个清单不需要背它是从几十道链表题里沉淀出来的一套固定自检。每写完一个解法在提交前对照走一遍能把很多低级错误挡在门外。5. 链表题的递归视角从“指针搬运工”到“递归思想家”5.1 递归的本质是定义清晰的小问题链表天然适合递归因为链表的结构本身就是自相似一个节点后面接的仍然是一个链表。很多链表的复杂操作如果从递归视角看会简洁到让人怀疑。以反转链表为例递归写法比迭代短很多def reverseList(head): if not head or not head.next: return head newHead reverseList(head.next) head.next.next head head.next None return newHead我在第一次看到这个解法时内心是拒绝的因为它太“反直觉”了反转整个链表竟然要先递归处理除头节点外的剩余链表。但理解了递归的“信任”之后这条代码反而成了我最常用的反转写法。递归的关键是两点基线条件base case和递推关系recursive relation。基线条件是head为空或只有一个节点此时无需反转直接返回递推关系则是“反转以head.next开头的子链表再把head接到子链表尾部”。head.next.next head这行核心逻辑其实就是在建立“子链表尾指向head”的新连接。5.2 不要试图“走进”递归而是试着“站在外面”描述递归初学者学递归最大的误区是试图在脑子里把每一层递归都展开。面对链表递归更合适的姿势是相信这个递归函数能完成它名字所描述的事情然后只关注当前这一层需要做什么。拿合并两个有序链表来举例递归代码看起来特别像“废话文学”如果list1的值小就选择list1并把list1的next改成“合并list1-next和list2的结果”然后返回list1。这里完全没有考虑后续具体怎么合并因为我们已经授权递归函数去做了。这种写代码的方式和迭代思维完全不同。迭代是“我亲眼看着每一步发生”递归是“我定义清楚问题然后把解决过程交给函数自己”。刷链表题时每道题至少尝试写一遍递归版本会对理解函数式思维很有帮助这比单纯背代码重要得多。5.3 递归与迭代的选择面试中的三层递进如果面试中遇到链表题我的建议是先问自己三个层次能不能想出暴力解这个阶段哪怕O(n^2)都行先保证有答案能不能优化成一次遍历的迭代解这是多数题目期望的解法空间O(1)能不能写出递归形式递归往往代码最短、最优雅但要注意递归栈深度和可解释性。不要一上来就追求最优解更不要只会背最优解。面试官常见套路是让你先写递归再让你改成迭代或者反过来。两个版本都准备才能顺利接招。6. 刷题链表的常见错误排行榜Top 5 与对应改法6.1 错误一忘了保存next指针这个错误几乎每个链表新手都会犯。典型场景是反转链表或者插入节点时先改了cur-next但原本的下一个节点地址没有保存直接导致链表后半段丢失。改法很简单任何修改next的语句之前先想想这个节点的原next是否还需要被访问。需要的话就先存进一个临时变量。对比一下错误写法与正确写法// 错误 cur-next prev; cur cur-next; // 此时cur已经指回prev死循环 // 正确 ListNode* nextTemp cur-next; cur-next prev; prev cur; cur nextTemp;这一类bug的隐蔽性在于代码不报错只是运行结果不对甚至可能死循环。排查的时候返回去看链表是否成环也是这个思路。6.2 错误二空指针访问cur-next-next这种写法在cur-next已经是nullptr时会直接崩溃。典型出没场景是快慢指针或者两两交换节点。比如节点数为奇数的链表最后一对交换时只有一个节点代码如果没有加保护就会越界。改法是在访问cur-next-next之前确认cur-next不为空。必要时可以加上while (cur-next ! nullptr)的条件或者在循环条件里多写一个判断。6.3 错误三返回值返回了dummy而不是dummy-next使用了虚拟头节点之后很多人最后return dummy结果整个链表前面多了一个值为0的节点。这个错误在本地调试时不容易发现因为打印结果看起来只是多了一个0但LeetCode判题时会直接类型错误之类的反馈。我在自己的代码里已经形成了刻板习惯**用了dummy最后一定return dummy-next。**如果题目要求返回头节点本身那就把dummy删掉再返回。6.4 错误四删除节点后没有释放内存C里new出来的节点需要手动delete否则会内存泄漏。刷题时这个影响不明显但项目里如果大量动态创建节点却不释放内存会越占越多。建议是每次删除节点时先用临时变量保存要删除的节点指针然后让它“失联”——即prev-next cur-next——最后再delete cur。顺序不能反先delete再取cur-next是悬空指针访问。6.5 错误五修改了头指针导致“找不到门”很多链表操作需要移动头指针来遍历比如head head-next循环。如果最后需要返回原链表头而你的head已经在循环中走到了末尾返回的就会是nullptr或者末尾节点。解决办法有两个一是在遍历前用另一个变量保存头节点二是直接不修改head而是用cur来遍历。后者更干净也更符合大多数题的返回值要求。7. 链表题的经典组合题设计链表与环形链表7.1 设计链表实现get、addAtHead、addAtTail、addAtIndex、deleteAtIndex力扣707题“设计链表”是一个综合检验链表基本功的好题。它要求实现一个链表类的五个方法这几乎覆盖了链表的全部基本操作。我自己在做这道题时就是把虚拟头节点用到了极致五个方法没有一个是靠单独处理头节点来写的。核心要点是维护一个size记录链表长度维护dummy头节点。获取第index个节点时如果index无效小于0或大于等于size返回-1添加节点时找到前驱位置插入删除时同样找前驱。由于所有操作都是基于dummy展开头节点只是dummy-next代码结构非常统一。7.2 环形链表判断成环与寻找入口环形链表有两个考点判断链表是否有环以及找到环的入口。判断有环用快慢指针很经典慢指针每次走一步快指针每次走两步如果二者相遇则有环否则无环。寻找环的入口则有一种数学上很优美的结论快慢指针相遇后从相遇点和头节点同时出发每次各走一步再次相遇的位置就是环入口。这个结论我第一次学时觉得像魔法后来自己推导了一遍公式才真正理解。为什么快慢指针相遇时两者离入口的距离和头节点到入口的距离相等关键在于快指针比慢指针多走的距离是环周长的整数倍。我的建议是这类结论不能只背最好在纸上把两轮的“步数方程”列一遍。一旦理解了原理即使面试时忘记了结论也能从公式反推出来比硬背牢靠得多。8. 链表刷题节奏与训练建议从day3往后走的路8.1 给新手的刷题顺序建议如果你刚进入链表章节我推荐按这个层次安排练习基础操作热身反转链表迭代法删除倒数第N个节点合并两个有序链表结构变换类两两交换链表中的节点旋转链表重排链表环与交点类环形链表环形链表II相交链表综合设计类设计链表LRU缓存进阶。每一步都要保证代码细节完全自己写出来而不是看完答案回忆着敲。复盘时给自己提三个问题这个题用了什么核心技巧虚拟头/快慢指针/递归如果输入是空链表、单节点、尾节点代码会怎样能不能改成另一个版本的写法迭代改递归/递归改迭代8.2 如何复盘一道链表题我复盘链表题时有一个固定套路关闭题解页面靠自己从题目描述推导出解法。推导顺序严格按照“明确数据结构 → 画图模拟一轮 → 写伪代码 → 用边界用例验证”。写完代码之后用以下三个用例做自检空链表、只有一个节点、正常长度链表然后看最终返回结果是否符合预期。这个过程廉价高效能覆盖绝大多数低级错误。8.3 链表题在真实面试中的考察点我在实际面试和模拟面试中观察到链表题很少单独考察“你有没有背过这道题的答案”更多是考察四个方面对指针/引用的理解是否扎实对边界条件的敏感度是否能自行选择合适的方法虚拟头节点、快慢指针、递归等写代码是否干净是否一边写一边能解释自己在干什么。因此即便你已经刷过三道重复的链表题每一道仍然值得亲手写完。链表的指针操作只有动手写到形成肌肉记忆才能真正在面试紧张的状态下依然保持稳定的代码质量。9. 总结从day3链表结束到下一个知识模块的衔接思路链表刷完之后你开始具备“动态结构”的思维下一个自然过渡是哈希表或递归。比如环形链表的入口问题就需要哈希表记录访问过的节点反转链表的递归版本又直接练到递归函数设计。这个承接关系告诉我每一章都不是孤立的。我自己对链表章节的体会有三点也是我最想传递给读到这里的你的所有看似复杂的链表操作几乎都建立在三个基础动作上找前驱、改指针、记next。把这三个动作用到滚瓜烂熟其他题都是“换皮不换骨”虚拟头节点值得成为默认标配它统一了边界降低了思考成本画图是链表题最好的debug工具没有之一。最后分享一个我反复用的小技巧刷链表题时不要只在题库里做题有空就自己手动构造链表练习增删改查全套操作。当你能不看代码徒手写出一个完整的链表类时这一章才算真正过关。第二天回头看时你会明显感觉到对指针的掌控感已经不一样了。
阅读完成 · 觉得有帮助？
