今天按《代码随想录》的训练节奏正式进入day4这一天的内容集中在我个人觉得整个链表章节里最需要手感的三个题反转链表、两两交换链表中的节点、删除链表的倒数第N个节点。前几天的移除链表元素、设计链表还只是单一节点操作到了这三题会把指针改向、循环不变量、哨兵节点、快慢指针全串起来。很多刷题人都有同一个感受数组题看题解是能看懂的链表题看了题解也总觉得“懂了”但一合上答案自己写立刻断链、漏接、空指针访问。这个现象非常正常因为链表问题的核心根本不是“背下来”而是你要在脑子里维护好几条同时存在的指针关系每一次“先改A还是先改B”都会直接影响后面能否继续遍历。这篇文章就围绕day4这三道题把每一步为什么要这么写拆开讲清楚适合正在跟《代码随想录》训练营打卡的人也适合所有被链表操作折磨过的新手。1. Day4 真正卡人的地方链表的“断链”与“接链”1.1 为什么数组能闭眼写链表不行数组和链表在内存布局上的差异决定了写法思维完全不同。数组是一片连续内存下标可以直接定位你写arr[i 1]永远知道下一个元素在哪哪怕你刚改过arr[i]也不影响arr[i 1]的访问。链表不一样每个节点散落在堆里当前节点只通过next指针告诉你去哪找下一个节点。你可以把它理解成一种“单线联系”的关系网A认识BB认识C但A没有C的联系方式。如果你在遍历过程中把A的“通讯录”改成了别人那B和C这条线就断了后面整个链表都找不回来。数组操作里最常见的错误是下标越界但下标越界一般报错很明确。链表操作里最常见的错误是“莫名其妙丢了节点”它不报错程序甚至能继续跑只是链表的长度变短了或者形成一个环最后输出结果完全不对。这种错误最难查因为你很难从控制台里一眼看出谁丢了。我在day4之前对链表也算熟悉能写出单链表反转的代码但仅限于把代码背下来了。真正让我意识到问题的是两两交换这道题一开始的写法是先让cur-next指向第二节点再倒回来让第二节点指向第一节点结果第三个节点直接找不到了。后来排查才发现我在改cur-next之前没有把第二节点原有的next保存下来。这一天练习的本质就是把“改指针之前先保存后继”这个习惯练成肌肉记忆。1.2 今天三题背后的公共套路这三道题看上去各不相同一个要反转方向一个要成对交换一个要删除指定位置的节点但底层有两个公共套路是相通的。第一个套路是“先保存后断链”。凡是要改变某个节点的next指向都得考虑原指向是否还需要。反转链表里要保存cur-next因为等下cur-next就要指向前驱不保存就丢掉了后面的整段链表。两两交换里要保存得更小心因为会连续改好几条next。删除倒数第N个节点时虽然看似没有大规模改向但你仍要先把待删除节点用临时变量存下来否则执行slow-next slow-next-next之后那个被删除的节点就彻底没引用内存都释放不了。第二个套路是“给头节点配上虚拟头节点”。链表里最尴尬的节点永远是头节点因为其他节点都有前驱改指针时可以通过前驱操作头节点没有前驱想删除或交换头节点就得单独写分支。这个问题最优雅的解法就是加入一个dummyHead让真正的头节点也变成一个“有前驱的普通节点”。今天的三道题里两两交换和删除倒数第N个节点都属于“头节点可能被改动”的场景所以使用虚拟头节点几乎是必须的。反转链表其实可以不用但如果你用虚拟头节点反而容易把思路带偏。这个取舍我在第2节会细讲。除了这两个套路删除倒数第N个节点还额外用到快慢指针这也是链表中处理“不知道长度”问题的一个经典手段。链表不像数组可以直接拿length - n来定位它只能从前往后走。但你可以用一个“间距固定”的双指针把倒数问题转换成正数问题本质上就是高中数学里“相对速度”的意思。2. 虚头节点今天必须先想清楚的辅助节点2.1 它解决的是什么问题虚拟头节点是一个附加在真实头节点前面的哨兵节点它不存储业务数据只是一个占位符。假设原链表是head - A - B - C加上虚拟头后就是dummyHead - A - B - C代码里统一通过dummyHead-next来访问原来的头节点。为什么这个占位符这么重要看一个最简单的操作删除头节点。如果没有虚拟头节点你要写head head-next这本身不复杂但如果你是在一个循环里做条件判断比如“找到值等于 target 的节点就删除”头节点和其他节点就得分两套逻辑写。头节点时直接改head非头节点时得找到前驱再改prev-next。这种分支不仅代码难看还特别容易漏。有了虚拟头节点之后头节点就不再特殊它也会有一个“前驱”叫dummyHead。所有删除操作都可以统一写成prev-next prev-next-next所有交换操作也都可以统一从dummyHead开始向后处理。实际上很多链表的边界 bug 都源于“头节点没有前驱”这个不对称问题加上虚拟头节点就是在源头上把不对称抹平。我自己总结了一个判断标准只要题目里存在“删除头节点”“交换前两个节点”“在头部插入节点”这些可能改变头节点的操作就优先使用虚拟头节点。它能帮你把单个节点的特判全部去掉。这里的取舍不是“会不会写特判”的问题而是“特判写多了边界条件容易看漏”。反而用虚拟头节点后循环里的代码模式高度统一出错概率小很多。2.2 什么时候需要虚拟头节点什么时候不需要虽然虚拟头节点很好用但也不是无脑加。反转链表就不用。反转链表的迭代写法里pre初始设为nullptrcur从头节点开始这个pre本身就是头节点的“前驱”所以不需要额外造一个哨兵。如果你非要在反转里再加虚拟头节点会让指针的初始关系变复杂反而得不偿失。下面这张表可以帮你快速判断今天这几类场景的使用倾向场景是否建议虚拟头节点原因删除头节点 / 删除任意已知前驱的节点是让头节点也有前驱统一删除逻辑两两交换相邻节点是每次循环都要从要交换节点的前驱开始操作反转整条链表否用prev nullptr直接充当头节点的前驱即可删除倒数第N个节点是可能删到头节点且慢指针需要从虚拟头节点起步定位前驱查找中间节点 / 判断是否有环视情况不涉及头节点变更时不一定需要哨兵使用虚拟头节点时还有一个容易踩的坑最后返回的一定是dummyHead-next不是原来的head。原因是经过交换或删除后原来的head可能已经不在链表最前面了。比如两两交换中原head变成了第二个节点如果你返回head直接从第三个节点开始输出了这题必错。我见过很多人在本地测试时不报错一提交就失败就是返回变量写错。还有一个小提示dummyHead是用new手动申请出来的严格来说应该在使用结束后释放。LeetCode 的测试环境一般不会检查内存泄漏所以很多题解直接省略delete。但如果是在本地项目里做练习建议养成好习惯返回前用临时变量保存结果然后delete dummyHead。我后面给的代码为了可读性先不写释放你实际练习时可以自己补上。3. 三道题从思路到代码3.1 反转链表从“保存下一个”到递归反转链表是所有链表题里最基础的一道也是后面很多复杂题目的“零件”。它的要求很简单把1 - 2 - 3 - 4 - 5变成5 - 4 - 3 - 2 - 1不允许新建链表必须原地反转。迭代法的核心是维护两个指针pre和cur。初始时pre nullptrcur head每一轮都让cur-next指向pre然后整体向右移动一步直到cur遍历完整个链表。移动顺序必须是“先保存再改向再前进”如果把“保存”漏掉改完cur-next后cur原来的下一个节点就找不到了循环根本没法继续。ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 保存后继 cur-next pre; // 反转当前节点 pre cur; // pre 前进 cur next; // cur 前进 } return pre; // pre 最后指向新的头节点 }我在这个循环里最常问自己的问题是为什么前进的时候是先pre cur再cur next而不是反过来。顺序其实可以反先cur next再pre cur就错了因为cur已经指向next再执行pre cur会把pre指向next而不是当前节点。只要在纸上跟着画一次就能理解这个顺序问题。递归版本则完全是另一种思考方式。它不关心“从头到尾怎么一步步反转”而是假设“后面的链表已经反转好了”只需要处理当前节点和它的下一个节点之间的关系。代码很短但第一次看很难绕过来ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }递归里最关键的四行是先递归到链表的最后一个节点然后在每一层回归时执行head-next-next head。这句话的意思是让当前节点的下一个节点反过来指向自己。以1 - 2 - 3为例递归到节点3时返回节点2执行2-next-next 2也就是把3的 next 指向2然后把2-next置空。这时得到1 - 2 - 3然后节点1再执行1-next-next 1把2的 next 指向1再把1的 next 置空最后得到3 - 2 - 1。很多初学者漏掉head-next nullptr结果链表尾部会留一个环程序能跑但会死循环这是最隐蔽的错误。复杂度层面迭代法时间 O(n)额外空间 O(1)递归法时间 O(n)但由于递归栈深度为 n额外空间 O(n)。面试时如果追问空间复杂度通常偏好迭代版本。3.2 两两交换先处理远的关系再处理近的关系题目本身不难理解把链表相邻的两个节点交换位置但不能改节点里的值只能改指针。1 - 2 - 3 - 4变成2 - 1 - 4 - 3如果链表长度是奇数最后一个节点保持原样。这道题非常训练“同时维护多条指针关系”的能力。因为交换两个节点时你不只要改这两个节点之间的互相指向还要处理好前驱节点与后继节点之间的连接。如果链表是0(虚拟头) - 1 - 2 - 3 - 4现在要交换1和2。首先要站在“1和2的前驱”也就是虚拟头节点cur的角度来看问题因为如果站在1本身你无法让前驱指向2。具体拆解成三步用node1记下cur-next节点1用node2记下cur-next-next节点2。node1-next node2-next让节点1先指向节点3把后面的链表接住。node2-next node1让节点2指向节点1完成两个节点的反转。cur-next node2让虚拟头节点指向节点2。把cur移到node1准备处理下一对。这个顺序非常讲究。为什么不能让cur-next node2放在最前面因为一旦cur-next从节点1变成节点2节点1的引用就丢了你后面既没法让node2-next node1也没法往下遍历。类似地如果把node2-next node1放在node1-next node2-next之前节点2原来的后继就丢了。我习惯把这类操作归纳成一句话先处理远的关系再处理近的关系。所谓“远的关系”是指 node1 与新后继 node3 的关系所谓“近的关系”是指 node2 与 node1 的关系以及 cur 与 node2 的关系。完整代码ListNode* swapPairs(ListNode* head) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* cur dummyHead; while (cur-next ! nullptr cur-next-next ! nullptr) { ListNode* node1 cur-next; ListNode* node2 cur-next-next; node1-next node2-next; node2-next node1; cur-next node2; cur node1; } ListNode* result dummyHead-next; return result; }循环条件cur-next ! nullptr cur-next-next ! nullptr表示当前节点后面至少要剩两个节点才需要交换。这两个条件必须都检查不能只查一个否则可能在cur-next为nullptr时继续访问cur-next-next直接对空指针做解引用。我在本地调试这道题时习惯在每轮循环后把链表整个打印出来跟踪cur的位置。有一次我发现输出一直是2 - 1 - 2 - 1后来才意识到是漏掉了第五步cur node1导致cur一直停在虚拟头节点程序反复交换前两个节点。所以当你发现输出长度没变、只是前两个节点无限交换时第一反应就应该是检查cur是否往前移动了。3.3 删除倒数第N个快慢指针制造“间距”题目要求一次遍历就完成删除。如果不知道链表长度正常情况下你得先遍历一遍数出长度再第二遍走到length - n的位置这是两次遍历。而快慢指针可以把这个过程压缩成一次。思路是让快指针先出发慢指针在原地等。快指针先走n 1步然后快慢指针以同样的速度一起走。因为两者的间距始终是n 1当快指针走到链表末尾的nullptr时慢指针恰好停留在待删除节点的前一个位置。这个前驱位置至关重要因为删除节点本质上是修改前驱的next指向而不是修改被删除节点本身。为什么是n 1而不是n稍微推导一下。如果快指针只先走n步那么快指针到末尾时慢指针正好落在待删除节点上。可此时你拿不到它的前驱节点单链表又没法回头。为了一次遍历就拿到前驱必须让慢指针比目标节点再慢一步站在前驱上所以快指针要走n 1步。有了这个理解代码就顺理成章了。额外加一个虚拟头节点是为了应对“要删的是头节点”这种边界情况。如果链表长度为3删除倒数第3个节点实际删的是头节点。这时候慢指针应该停在虚拟头节点上才能执行slow-next slow-next-next并把头节点摘掉。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead new ListNode(0); dummyHead-next head; ListNode* fast dummyHead; ListNode* slow dummyHead; // fast 先走 n 1 步 for (int i 0; i n 1 fast ! nullptr; i) { fast fast-next; } // 两者同步前进直到 fast 走到 nullptr while (fast ! nullptr) { fast fast-next; slow slow-next; } // slow 此时指向待删除节点的前驱 ListNode* toDelete slow-next; slow-next slow-next-next; delete toDelete; // 本地练习建议释放LeetCode 可省略 return dummyHead-next; }用1 - 2 - 3 - 4 - 5、n2来验证。虚拟头节点记为0初始fast 0slow 0。/ 到了3慢指针从0到了3。此时删除slow-next也就是节点4。结果是1 - 2 - 3 - 5正好删掉了倒数第二个节点。整个过程中链表只被完整遍历了一遍时间复杂度 O(n)空间复杂度 O(1)因为只用了两个指针。边界情况用表格验证更直观链表n快指针走过删除结果1-2-33走4步到nullptr慢指针留在虚拟头删除头节点1结果为2-31-2-31走2步到节点3然后同步走删除尾节点3结果为1-211走2步到nullptr慢指针留在虚拟头删除尾节点即头节点结果为nullptr这个推导是这道题最容易出错的地方。我见过有人把步数写成n最后输出删错了对象也有人把同步前进条件写成fast-next ! nullptr边界情况又全部偏移一个位置。最简单可靠的做法就是始终记住“慢指针要有前驱视角”所以在开始同步前先让快指针多走一步。4. 边界条件和排查实录4.1 我连续写错的三个位置第一处是反转链表的循环体顺序。最开始我写的是cur-next pre在前保存next在后结果第一次反转就把cur-next覆盖成了pre原本的next永远找不回来。这个错误在单节点链表上看不出来一旦链表一长就变成输出一个节点后直接退出。现在我把“先保存、再改向、后前进”九个字当成铁律只要动next就先问自己一句原来的next还有没有变量记着第二处是两两交换里的循环条件。我一度只写cur-next-next ! nullptr因为觉得能访问到第二个节点自然就说明cur-next不为空。但如果链表长度是0cur-next本身就是空再去访问cur-next-next就是对空指针操作程序直接崩溃。C 里的短路求值可以帮我们避免这个问题前提是必须把cur-next ! nullptr写在前面。第三处是删除倒数第N个节点时没有使用虚拟头节点。当时我觉得可以特殊判断一下单独处理“删除头节点”的情况结果写出了一堆if (slow dummyHead)之类的分支最后反而漏掉了一个 case。改成虚拟头节点后所有删除操作统一成一行代码边界全部消失。这也印证了前面说的链表题里很多复杂度不是问题本身带来的而是没用对工具。4.2 常见问题速查我把平时刷题时最典型的问题整理成一张排查表方便你遇到类似报错时直接对照。症状可能原因修复思路输出结果只有1个节点反转时没有保存cur-next链表断在第一次反转处在改next前用临时变量保存后继输出出现循环节点程序死循环尾节点的next没有置空反转时记得head-next nullptr两两交换时前两个节点无限交换cur没有向后移动每轮结束把cur赋值为node1访问空节点的成员报nullptr解引用循环条件里少了cur-next ! nullptr先用短路逻辑判断前一个节点不为空删除倒数第N个节点后删错对象快指针只走了n步慢指针停在待删节点而非前驱改成走n 1步头节点被删除后返回错误结果返回了原来的head返回dummyHead-next本地用delete后进程崩溃删除了仍需访问的临时节点确认所有引用关系已经断开后再释放还有一个隐藏问题值得提一下内存泄漏。LeetCode 的判题环境不会因为你new了虚拟头节点没删就判你错但它会在程序结束时统一清理。如果你在本地用真实项目跑每个测试样例都new一个不释放的虚拟头节点跑几百个用例内存就会看着涨上去。所以我个人在练习代码里会保留delete但如果你刚入门可以先把逻辑跑通再回头补内存释放不要因为内存问题干扰了算法学习的重点。5. 第四天的练习建议与节奏5.1 从看懂到默写中间是“画图”很多人刷题有个误区看完题解觉得“这不难”于是直接开始敲代码。结果敲到一半卡住又回去翻题解看完再继续敲。这样反复几次后代码是写出来了但合上答案第二天又忘干净。链表题尤其不能这么学因为你对指针关系的理解是飘的没有变成自己的操作顺序。我建议的练习步骤是第一遍完全照着题解敲敲完运行通过第二遍不看代码但在纸上画出链表变化图把每一步的pre、cur、next或node1、node2都标出来直到能不看代码画出完整过程第三遍看着自己画的图把代码重新写一遍第四遍完全闭卷限时15分钟写一道。如果能走到第四遍这道题才算真正过脑了。有些初学者觉得画图浪费时间但链表题恰恰是最需要画图的题型。你在纸上画三遍比盯着屏幕看十遍都管用。因为链表操作本质上就是箭头的增删改画图能把“抽象指针”变成“可视箭头”。我通常用的是最简单的方式把节点画成小方框方框里写值右边画一个小框代表next等操作的时候直接在新方向画箭头旧方向打叉。这个过程慢是慢但特别治愈“一看就会、一写就废”的毛病。5.2 一道题多种写法怎么看day4的三道题里反转链表有迭代和递归两种主流写法删除倒数第N个节点也可以用栈来实现。新手建议先选定一种自己最有把握的写法作为主攻能力把另一种作为理解素材。不要逼自己今天就把递归彻底搞懂更不要背代码。理解每种写法的关键是回答三个问题终止条件是什么每轮操作处理几个节点返回值是谁以反转链表为例迭代版本的终止条件是cur nullptr每轮处理一个节点返回值是pre。递归版本的终止条件是head nullptr || head-next nullptr每层只处理“当前节点”和“下一个节点”之间的关系返回值是新的头节点。当你能把这三个问题讲清楚你就不是背代码而是真正理解了算法结构。后面遇到反转区间链表、反转一部分链表也能在现有模板上做改造。我还会在本地写一个简单的链表打印函数每一轮循环后都把head重新遍历并打印一遍。这样做直观到什么程度两两交换中哪怕cur没有前进你能在控制台里看到前两个节点被反复交换很快就能定位问题。链表题的调试难度很多时候源于“看不到状态”加一个printList函数所有过程全部显形。这个辅助函数其实就是四五行代码但对练习的帮助非常大。另外建议把那道经典的“给链表排序”或者“合并两个有序链表”留到day4之后做因为它们会频繁用到今天练的这些操作。反转的思路用于找中点后拆链表虚拟头节点的思路用于合并时简化头节点判断快慢指针的思路用于找中点。day4学的东西绝不是孤立的它基本是后续所有中等难度链表题的底盘。最后再分享一个小技巧每天刷完题不要急着开始新题把三题的代码翻出来看一眼回忆一下每道题的核心操作顺序。反转链表就记“保存、改向、前进”两两交换就记“先远后近再移动cur”删除倒数第N个就记“快指针走 n1”。这三个短句看起来简单但在面试现场紧张的时候短句比长代码可靠得多。按《代码随想录》这套循序渐进的方式把day4踩扎实后续链表相交、环形链表、合并链表这些题再出现时你会明显感觉顺手很多。