很多人第一次刷链表题的时候最烦的就是“倒数第N个”这种说法。链表跟数组不一样数组知道长度可以直接下标定位链表你不走到最后一个结点根本不知道总共多长更别提从后往前数了。这道“删除链表的倒数第 N 个结点”在很多题库里的编号不太一样有的平台标成19号有的标成106号但题目内核基本一致。别看它标注的难度不算高可它在面试现场出现的频率相当高因为这道题能同时考察你对链表结构的理解、边界条件的处理、双指针技巧的熟练度还有代码实现的稳健程度。我最初刷这道题的时候用的是最笨的方法先遍历一遍算出链表长度再走第二次找到目标结点的前驱把它删掉。虽然能过但总觉得不够优雅而且第一次提交还栽在了“删除头结点”这个边界上。后来我把快慢指针的解法彻底吃透了才发现这道题真正的价值在于你能否用一次遍历完成操作并且不引入额外空间同时面对各种边界情况都不出错。这篇文章就把我当时踩过的坑、总结的思路、试验过的代码版本以及推荐的标准解法完整梳理一遍。如果你正处于刷题初期或者准备面试想快速过一遍链表经典题这篇应该能帮上忙。1. 题目到底在考什么先还原一下题目本身的描述给定一个链表头结点 head 和一个整数 n删除链表中倒数第 n 个结点并返回链表的头结点。“倒数第 n 个结点”这个说法对刚接触链表的人来说很容易产生误解。有人会试图把链表翻转过来再删有人会尝试先找到尾结点再往前回溯还有人会想用递归的“回溯特性”来处理。这些思路不能说完全错误但多半会引入额外的时间或空间开销或者让代码复杂度无谓地上升。题目真正想考的核心其实可以拆成几个点。1.1 理解“倒数”的本质倒数第 n 个结点翻译成正面说法就是“正数第len - n 1个结点”其中 len 是链表的总长度。这个转换关系看起来简单但实际写代码时特别容易算错下标差一个位置就是删错结点的事故。举个例子链表有 5 个结点n 2那么倒数第 2 个结点就是正数第 4 个结点。为什么因为从最后一个结点往前数 1 个倒数第 2 就是从尾结点向左偏移 1 位对应正数第 4 位。这类“偏移量”问题建议每个做题的人都自己画一个 5 结点的链表图标出每个结点的正数和倒数位置比死记公式要靠谱得多。1.2 单链表的天然限制单链表每个结点只能通过 next 指针向后访问无法像数组那样通过索引直接跳转也无法回头访问前驱结点。这带来两个直接影响删除一个结点必须持有它的前驱结点的指针否则无法把前驱的 next 接到被删结点的 next 上。“从后往前数”的操作天然无法直接在单链表上做除非提前知道链表的长度。所以这道题的所有解法本质上都在回答同一个问题如何在不知道链表长度的情况下或者虽然知道长度但不想遍历两遍的情况下定位到目标结点的前驱。1.3 边界条件才是真正的分水岭我见过很多能把主思路讲得清清楚楚的人一写代码就挂挂的地方翻来覆去就那么几个n 等于链表长度此时要删的是头结点单独处理 pre 指针为空的情况。链表只有一个结点删完返回空指针 null。n 小于 1 或大于链表长度题目通常会给出约束说明但面试时最好主动确认。删除的恰好是最后一个结点此时被删结点的 next 是 null不影响前驱的接续逻辑但容易让人在理解上打结。这些边界条件的处理方式往往才是面试官真正想听的部分。因为核心思路大家都能想到能把边界写对、写稳才说明确实理解了链表操作的本质。2. 解法一两次遍历法先聊最直观、最不容易出错的版本。既然“倒数第 N 个”的核心困难在于不知道链表长度那我们就先遍历一遍得到长度再走第二遍去删除。思路简单到不需要任何技巧非常适合作为第一个 AC 版本也适合在没思路的时候先写出来保底。2.1 完整代码示例下面是我用 Java 实现的版本关键步骤都有注释。public ListNode removeNthFromEnd(ListNode head, int n) { if (head null || n 0) { return head; } // 第一轮数出链表总长度 int length 0; ListNode cur head; while (cur ! null) { length; cur cur.next; } // 如果要删的结点本身就是头结点直接返回 head.next if (n length) { return head.next; } // 目标结点的前驱从头结点开始移动 length - n - 1 步 ListNode pre head; for (int i 1; i length - n; i) { pre pre.next; } // 删除目标结点目标结点就是 pre.next pre.next pre.next.next; return head; }2.2 为什么这段代码要先跑两轮很多人第一次看到这个方法会觉得“这也太直白了吧”但直白恰恰是它的优势。第一轮遍历只用来看长度不修改任何引用第二轮遍历通过 length - n 来计算前驱的位置。这里最容易算错的地方在于前驱需要移动 length - n - 1 次还是 length - n 次两种写法对应循环的初始值不同一旦写错要么删的是前一个结点要么压根没移动到位。我建议你在草稿纸上画一条长度为 5 的链表n 2手动跑一遍 for 循环的每一步。节点编号从 1 到 5前驱是 3 号结点从 head1 号开始需要移动两步才能到达 3 号结点而 length - n 3所以 for 循环从 i 1 开始循环条件是 i 3总共执行两次。这样把推导写一遍基本上就不会再犯傻。2.3 这个方案的优劣势优点非常明显思路简单代码可读性高几乎不存在“想不出来”的问题。缺点也同样明显链表只能顺序访问求长度必须完整遍历一次删除又需要遍历到目标位置附近因此整体时间复杂度是 O(L)其中 L 是链表长度但实际遍历次数接近 2L。在对时间复杂度要求不高的场景下这已经足够了。不过如果在面试里只给出这个方案面试官大概率会追问一句“能不能只遍历一次”这就引出了下面要说的快慢指针法。3. 解法二快慢指针法快慢指针是链表题里出镜率极高的一类技巧合并链表找中点用它判断链表有没有环用它这道题里它也能让“只遍历一次就能删除倒数第 N 个结点”变成现实。我第一次学会这个思路时觉得设计得真巧妙说白了就是用一个“人为制造的间距”来抵消“未知长度”带来的麻烦。3.1 核心思路既然我们要删除倒数第 n 个结点等价于找到一个位置它距离链表末尾正好 n 步。我们可以在链表头部设置两个指针 fast 和 slow先让 fast 前进 n 步这样 fast 和 slow 之间就差 n 个结点。随后再让 fast 和 slow 以相同速度前进每次各走一步。当 fast 到达链表末尾的 null 时slow 正好停在倒数第 n 个结点上。但你马上会发现一个细节我们要删除的是倒数第 n 个结点而删除操作需要前驱结点。如果 slow 正好指向目标结点本身我们还需要额外记录它前一个结点是谁。这可以有两种处理方案用另一个指针 preSlow 始终记录 slow 的前一个位置。更常见的做法是让 fast 先走 n 1 步这样当 fast 走到 null 时slow 正好停在目标结点的前驱位置。我推荐第二种因为省代码、理解起来也顺。但要记住使用第二种方案时我们需要保证 fast 在走 n 1 步时不越界而绝大多数题目会保证 n 不超过链表长度因此 fast 可以先走 n 步再判断是不是 null决定是否追加一步。3.2 标准代码实现下面是 Java 版本的快慢指针解法。为了统一处理“删除头结点”这种边界我引入了一个虚拟头结点 dummy。这个技巧在链表删除类题目中很常见值得单独说一说。public ListNode removeNthFromEnd(ListNode head, int n) { // 虚拟头结点避免单独处理“删除头结点”的逻辑分支 ListNode dummy new ListNode(0); dummy.next head; ListNode fast dummy; ListNode slow dummy; // 先让 fast 走 n 1 步 for (int i 0; i n; i) { fast fast.next; } // 再让 fast 和 slow 同步前进 while (fast ! null) { fast fast.next; slow slow.next; } // 此时 slow.next 就是待删除的结点 slow.next slow.next.next; // 返回虚拟头结点的 next也就是真正的头结点 return dummy.next; }只是实际写代码的时候还有个问题如果链表长度正好等于 n那 fast 先走 n 步就已经指向 null再走第 n 1 步就会空指针。所以更稳健的写法是分两步走public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode fast dummy; ListNode slow dummy; // 第一步fast 先走 n 步 for (int i 0; i n; i) { fast fast.next; } // 第二步fast 再走一步如果 fast 已经是 null说明 n 等于链表长度 // 要删的是头结点此时 slow 保持不动即可 if (fast.next ! null) { fast fast.next; } // 同步前进 while (fast ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }3.3 为什么快慢指针能一次遍历解决问题关键在于 fast 提前走出的“距离差”代替了“计算链表长度”的过程。我们不需要知道链表总量有多少只需要让 fast 和 slow 之间永远保持 n 步的间距然后一起走到终点。这个过程里fast 和 slow 加起来总共也只遍历了一次链表因为 fast 在前面开路slow 被动跟进二者不会重复走同一段路。这个思路的生活化类比是你和一个朋友在跑道上跑步你先让他跑出一段固定距离比如 10 米然后你们俩速度相同地同时往前跑。当朋友到达终点时你距离终点正好是那 10 米。那道题里这个“10 米”就是 n 个结点而你所在的位置就是倒数第 n 个结点。4. 边界条件与哑结点技巧链表题和数组题最大的区别之一就是链表题的边界情况特别多且特别容易导致代码崩溃。数组越界会抛异常链表操作错了往往直接出现环或者丢结点调试起来非常痛苦。所以每次写完链表代码我都会先跑一遍边界用例再提交。这段我把这道题里所有值得注意的边界情况全部列出来并给出处理建议。4.1 删除头结点的情况当 n 等于链表长度时倒数第 n 个结点就是头结点。如果你不使用虚拟头结点那么删除头结点的操作需要特判直接将 head 指向 head.next。很多初学版本的代码里一旦忘记这个特判就会出现一个诡异的现象删除倒数第 n 个结点后链表前段被丢掉了。我当时第一次写两次遍历法时就是在这个地方错的。原因是循环计算前驱位置时length - n 等于 0前驱从 head 开始走 0 步得到的 pre 还是头结点然后执行 pre.next pre.next.next结果把第二个结点给删了头结点反而没动。这种情况不好排查因为链表长度如果是 5删除倒数第 5 个结点正常结果应该是删掉第一个结点而我却删掉了第二个。这种情况后来我改成用哑结点统一处理就再也不需要考虑这种偏置问题了。4.2 哑结点为什么能统一逻辑哑结点是人为在头结点之前增加的一个额外结点值为多少无所谓关键在于它给链表补了一个“虚拟前驱”。有了它删除头结点这件事就从“单独处理 head”变成了“正常处理一个普通结点”因为头结点的前驱已经由 dummy 充当了。使用哑结点的框架大致是这样创建 dummydummy.next head。所有指针初始化都从 dummy 开始而不是从 head 开始。最终返回 dummy.next而不是 head。这样做还有个好处即使原 head 被删除了dummy.next 也已经自动指向新的头结点。这套处理方式在“删除指定结点”“合并两个链表”等很多链表题里都通用。学会了以后你能省下大量处理边界的精力。4.3 链表只有一个结点时会发生什么如果链表只有一个结点n 1这意味着要删除这个唯一的结点。删除之后链表应该变为空。使用哑结点方案时fast 先走 n 1 步由于 dummy 是虚拟头fast 走到原 head 结点然后判断 fast.next此时 fast.next 为 null因此跳过额外的一步进入 while (fast ! null)。由于 fast 不为 null它指向原 headslow 和 fast 各走一步fast 从原 head 移动到 nullslow 从 dummy 移动到 head 结点。最后执行 slow.next slow.next.next也就是 head.next null因为 head.next 本来就是 null所以链表收缩为空返回 dummy.next 为 null。整个过程不会出现空指针异常。如果不使用哑结点这个问题会变得更敏感slow 初始化指向 headfast 往后再走很容易出现 slow 为 null 或者 fast 为 null 的混乱状态。这就是强烈推荐哑结点的原因。4.4 n 不合法时的处理策略通常题目会限制 n 的范围确保 1 n 链表长度。但面试时最好主动和面试官确认一下如果 n 超出了这个范围应该怎么处理。有些版本会直接返回 null有些会选择抛异常有些则忽略非法输入。严格来说这不是算法题本身的核心矛盾所以多数刷题站点不会把它设计成隐藏测试用例。但你写工程代码时不能假设输入一定合法至少要在函数入口做防御性判断。写法和意图都清晰同时不会干扰正常逻辑。5. 复杂度分析与两种解法对比到了这一节我们可以站在更高的维度审视一下两种做法。面试中讲完代码之后面试官几乎必然会追问时间复杂度和空间复杂度因此提前把这个讲清楚很有必要。5.1 时间复杂度的准确测算两次遍历法的时间开销由两部分组成第一次遍历完整链表计算出长度 L访问次数为 L。第二次遍历到目标结点的前驱最多访问 L 次。所以总访问次数大约是 2L 量级时间复杂度记作 O(L)。快慢指针法需要 fast 从 dummy 出发走 n 步建立间距然后 fast 和 slow 同步前进。fast 实际走过的结点数大约为 L 1slow 走过的结点数也在这个范围内两者总访问次数接近 2L。因此从严格意义上说快慢指针法的时间复杂度同样是 O(L)只是它省去了“第一次完整遍历”的独立环节把两次遍历合成了一趟。在很多刷题教程里会直接说“快慢指针法只遍历一次”这里要澄清一下从语义上是“一次遍历”从访问次数上是“仍然需要走到链表末尾”但确实比两次独立的遍历更简洁。也有一种优化思路是从头结点开始先让 fast 走 n 步然后再同时出发这样 fast 的访问次数大约为 L - n 1slow 的访问次数也大致如此总访问次数会略小于 2L。但代码实现上对边界的处理会更麻烦我权衡之后还是推荐从 dummy 出发的标准写法稳定性优先。5.2 空间复杂度分析两种方案都不需要额外的链表存储空间只使用了若干个指针变量所以空间复杂度都是 O(1)。这里要注意Java 里的 ListNode 对象本身是题目给出的不算入我们额外申请的空间。如果你在解题过程中创建了额外的数组来存放结点引用那空间复杂度就会变成 O(L)面试时很容易被扣分。5.3 两种方案的适用场景简单总结来说方案时间复杂度空间复杂度代码难度边界处理适用场景两次遍历O(L)O(1)低需要单独处理头结点日常工作、快速 AC快慢指针O(L)O(1)中配合哑结点更稳面试展示、单次遍历需求递归回溯O(L)O(L)中高依赖栈空间练习递归思想不推荐用于面试关于递归方案我简单提一句可以通过递归返回到当前层的“位置信息”来判断当前结点是否为倒数第 n 个。思路很巧妙但由于递归深度等于链表长度空间复杂度是 O(L)在链表很长时可能爆栈所以不管是面试还是工程实践都不如两个 O(1) 空间方案好用。6. 常见错误与现场排查实录这里整理的是我刷这道题和给其他人 review 代码时遇到过的高频问题。每一个都是真实踩过的坑不是理论推演。6.1 空指针异常症状程序一运行就抛 NullPointerException位置在 fast.next 或 slow.next 附近。原因分析最常见的是 fast 先走 n 1 步时链表长度本身就只有 n 个结点fast 在第 n 步之后已经指向 null再访问 fast.next 直接就崩。有一种解法直接写 for (int i 0; i n; i)却忽略了 n 恰好等于 length 时 fast 会变成 null 这一点。排查方法在 fast 走完第一步和第二步之间加一个条件判断if (fast.next ! null)。如果 fast.next 是 null说明 fast 已经是尾结点此时 fast 不能再向前走了直接进入同步阶段即可。另外哑结点的存在也能减少指针为 null 的概率因为 slow 初始从 dummy 出发不会在一开始就指向真实头结点。6.2 删掉的结点不对症状链表没报错返回结果也正常但被删除的结点位置偏了一位比如删了倒数第 n 1 个结点。原因分析这几乎都是“间距”没有调整正确导致的。fast 先走 n 步的话最后 slow 指向的是目标结点的前驱而不是目标结点本身。如果循环里写成 i n 而不是 i n或者多走了一步的时候判断没做好slow 的停位就会偏差。排查方法把自己代入最极端的例子。假设链表只有 3 个结点n 1也就是删除最后一个结点。手动跑一遍fast 从 dummy 出发先走 1 步到达结点 1因为 fast.next 不是 null是结点 2fast 再走 1 步到达结点 2。随后 fast 和 slow 同步前进fast 从结点 2 走到结点 3 再走到 nullslow 从 dummy 走到结点 1。此时 slow.next 是结点 2也就是我们要删除的倒数第 1 个结点而实际的倒数第 1 个结点明明是结点 3。这就发现间距错了正确的做法是 fast 先走 n 1 步。这个例子是最容易定位问题的我建议每个遇到这类 bug 的人都亲手走一遍。6.3 头结点被吞掉症状删除操作执行后链表从第二个结点开始原来的头结点没了。原因分析这种情况多半发生在没有使用哑结点、且删除目标就是头结点的时候。因为 slow 初始指向 head如果 n 等于链表长度slow 经过若干步后停在了头结点然后执行 slow.next slow.next.next相当于删除了第二个结点而头结点没有变化。再细看返回结果是 head但 head 没被删。看起来好像是“链表丢了一个结点”实际上是把第二个结点误删了。排查方法优先使用哑结点方案。如果坚持不用哑结点那就在循环前判断 n length并将 head 指向 head.next。6.4 返回值写错症状逻辑全对但最终 return 的是原 head而原 head 恰好已经被删了。原因分析这个错误常常出现在脑子已经混乱的复盘环节。使用哑结点时如果返回 head而 head 已经被删除实际上返回的是一个没有被链表引用的孤立结点虽然它的 next 还能连到后面的结点但它本身不应再作为链表头。正确做法永远返回 dummy.next。在未删除头结点时dummy.next 就是原 head在删除头结点后dummy.next 自动更新为新头结点。6.5 调试技巧用打印法快速定位我会在关键位置打印当前指针指向的结点值比如每次循环开始时打印 fast.val 和 slow.val。虽然刷题平台上会限制输出格式但在本地调试时这招非常管用。举例来说输入链表 1 - 2 - 3 - 4 - 5n 2我在快慢指针同步阶段看到的输出应该是fast2, slow0 fast3, slow1 fast4, slow2 fast5, slow3 fastnull, slow4这个最后一行很关键当 fast 为 null 时slow 停在结点 4而倒数第 2 个结点是结点 4不对倒数第 2 个结点应该是 4这里我故意留个坑让你自己跑一遍。实际上链表 1 到 5 的倒数第 2 个结点是 4按理说 slow 应该停在 4 的前驱即结点 3。正确打印应当是最后一行 slow3。如果打印结果显示 slow4说明 fast 先走的步数太多或太少间距偏了。7. 扩展思考与实战建议这道题能延展出的点其实不少我整理了一些值得深入的方向适合刷完题之后再做一点思维体操。7.1 变形一删除倒数第 N 个结点并返回头结点这是标准版本本文已经详细讨论。重点注意哑结点的使用。7.2 变形二找到链表的中间结点这道题同样可以用快慢指针不过速度不同快指针一次走两步慢指针一次走一步。当快指针到达末尾时慢指针停在中间位置。它跟路径可复用先走 n 步建立间距再同步前进。7.3 变形三判断链表是否有环快慢指针的经典应用。快指针每次走两步慢指针每次走一步如果存在环两者最终会相遇。这类题和删除倒数第 N 个结点共享同一个思想工具库但边界条件差异很大建议放在一起刷。7.4 变形四删除链表中所有值等于目标值的结点去掉“倒数第 N 个”的限制改为按值删除。此时同样强烈推荐哑结点因为头结点本身就可能需要被删除。这道题可以很好地检验你是否真的理解“删除依赖前驱”这一约束。我个人的经验是把这几道链表题放在一起对照着刷复习效率比孤立刷单题高很多。7.5 手写代码时的习惯建议统一用 dummy 结点处理链表删除类问题能省一半的边界思考。写完代码后先跑空链表、单结点链表、删除头结点、删除尾结点这四类用例。尽可能抽一个独立函数用于创建链表和打印链表方便本地调试。面试时先在白板上画链表示意图把指针移动路径画出来再动手写代码。画图的过程本身就是在做边界验证。8. 最后的几点个人体会刷了这么多年算法题链表题一直是我觉得“看起来简单、写起来容易翻车”的类型。最近一次复习这道题时我又重新把两种解法写了一遍发现即使已经写过很多遍如果不集中精力边界条件依然可能出错。所以如果你想彻底掌握这道题光靠看文章是不够的必须自己动手在编辑器里敲一遍再打断点调试一遍最后再默写一遍。三遍下来你对单链表结构的感觉会明显不一样。还有一个小技巧做链表题时无论题目是什么先画图。我见过太多人拿到题就开始写代码写一半卡住了才发现自己搞错了指针方向。画图最多花两分钟但它能帮你省下二十分钟的调试时间。用箭头表示指针用方框表示结点把每一步变化都标注出来尤其在处理快慢指针时特别有效。这道题不是最难的链表题但它正好卡在“基础”和“技巧”的分界线上没有刁钻的数学推导也没有复杂的递归设计需要的只是你对链表结构本身的熟悉程度和对边界条件的敏锐性。把这题吃透后续再碰链表的反转、合并、排序、去重等问题会顺手很多。至少对我来说快慢指针这个解题工具就是从那段时间的反复练习里真正长在脑子里的。 很多人第一次刷链表题的时候最烦的就是“倒数第N个”这种说法。链表跟数组不一样数组知道长度可以直接下标定位链表你不走到最后一个结点根本不知道总共多长更别提从后往前数了。这道“删除链表的倒数第 N 个结点”在很多题库里的编号不太一样有的平台标成19号有的标成106号但题目内核基本一致。别看它标注的难度不算高可它在面试现场出现的频率相当高因为这道题能同时考察你对链表结构的理解、边界条件的处理、双指针技巧的熟练度还有代码实现的稳健程度。我最初刷这道题的时候用的是最笨的方法先遍历一遍算出链表长度再走第二次找到目标结点的前驱把它删掉。虽然能过但总觉得不够优雅而且第一次提交还栽在了“删除头结点”这个边界上。后来我把快慢指针的解法彻底吃透了才发现这道题真正的价值在于你能否用一次遍历完成操作并且不引入额外空间同时面对各种边界情况都不出错。这篇文章就把我当时踩过的坑、总结的思路、试验过的代码版本以及推荐的标准解法完整梳理一遍。如果你正处于刷题初期或者准备面试想快速过一遍链表经典题这篇应该能帮上忙。1. 题目到底在考什么先还原一下题目本身的描述给定一个链表头结点 head 和一个整数 n删除链表中倒数第 n 个结点并返回链表的头结点。“倒数第 n 个结点”这个说法对刚接触链表的人来说很容易产生误解。有人会试图把链表翻转过来再删有人会尝试先找到尾结点再往前回溯还有人会想用递归的“回溯特性”来处理。这些思路不能说完全错误但多半会引入额外的时间或空间开销或者让代码复杂度无谓地上升。题目真正想考的核心其实可以拆成几个点。1.1 理解“倒数”的本质倒数第 n 个结点翻译成正面说法就是“正数第len - n 1个结点”其中 len 是链表的总长度。这个转换关系看起来简单但实际写代码时特别容易算错下标差一个位置就是删错结点的事故。举个例子链表有 5 个结点n 2那么倒数第 2 个结点就是正数第 4 个结点。为什么因为从最后一个结点往前数 1 个倒数第 2 就是从尾结点向左偏移 1 位对应正数第 4 位。这类“偏移量”问题建议每个做题的人都自己画一个 5 结点的链表图标出每个结点的正数和倒数位置比死记公式要靠谱得多。1.2 单链表的天然限制单链表每个结点只能通过 next 指针向后访问无法像数组那样通过索引直接跳转也无法回头访问前驱结点。这带来两个直接影响删除一个结点必须持有它的前驱结点的指针否则无法把前驱的 next 接到被删结点的 next 上。“从后往前数”的操作天然无法直接在单链表上做除非提前知道链表的长度。所以这道题的所有解法本质上都在回答同一个问题如何在不知道链表长度的情况下或者虽然知道长度但不想遍历两遍的情况下定位到目标结点的前驱。1.3 边界条件才是真正的分水岭我见过很多能把主思路讲得清清楚楚的人一写代码就挂挂的地方翻来覆去就那么几个n 等于链表长度此时要删的是头结点单独处理 pre 指针为空的情况。链表只有一个结点删完返回空指针 null。n 小于 1 或大于链表长度题目通常会给出约束说明但面试时最好主动确认。删除的恰好是最后一个结点此时被删结点的 next 是 null不影响前驱的接续逻辑但容易让人在理解上打结。这些边界条件的处理方式往往才是面试官真正想听的部分。因为核心思路大家都能想到能把边界写对、写稳才说明确实理解了链表操作的本质。2. 解法一两次遍历法先聊最直观、最不容易出错的版本。既然“倒数第 N 个”的核心困难在于不知道链表长度那我们就先遍历一遍得到长度再走第二遍去删除。思路简单到不需要任何技巧非常适合作为第一个 AC 版本也适合在没思路的时候先写出来保底。2.1 完整代码示例下面是我用 Java 实现的版本关键步骤都有注释。public ListNode removeNthFromEnd(ListNode head, int n) { if (head null || n 0) { return head; } // 第一轮数出链表总长度 int length 0; ListNode cur head; while (cur ! null) { length; cur cur.next; } // 如果要删的结点本身就是头结点直接返回 head.next if (n length) { return head.next; } // 目标结点的前驱从头结点开始移动 length - n - 1 步 ListNode pre head; for (int i 1; i length - n; i) { pre pre.next; } // 删除目标结点目标结点就是 pre.next pre.next pre.next.next; return head; }2.2 为什么这段代码要先跑两轮很多人第一次看到这个方法会觉得“这也太直白了吧”但直白恰恰是它的优势。第一轮遍历只用来看长度不修改任何引用第二轮遍历通过 length - n 来计算前驱的位置。这里最容易算错的地方在于前驱需要移动 length - n - 1 次还是 length - n 次两种写法对应循环的初始值不同一旦写错要么删的是前一个结点要么压根没移动到位。我建议你在草稿纸上画一条长度为 5 的链表n 2手动跑一遍 for 循环的每一步。节点编号从 1 到 5前驱是 3 号结点从 head1 号开始需要移动两步才能到达 3 号结点而 length - n 3所以 for 循环从 i 1 开始循环条件是 i 3总共执行两次。这样把推导写一遍基本上就不会再犯傻。2.3 这个方案的优劣势优点非常明显思路简单代码可读性高几乎不存在“想不出来”的问题。缺点也同样明显链表只能顺序访问求长度必须完整遍历一次删除又需要遍历到目标位置附近因此整体时间复杂度是 O(L)其中 L 是链表长度但实际遍历次数接近 2L。在对时间复杂度要求不高的场景下这已经足够了。不过如果在面试里只给出这个方案面试官大概率会追问一句“能不能只遍历一次”这就引出了下面要说的快慢指针法。3. 解法二快慢指针法快慢指针是链表题里出镜率极高的一类技巧合并链表找中点用它判断链表有没有环用它这道题里它也能让“只遍历一次就能删除倒数第 N 个结点”变成现实。我第一次学会这个思路时觉得设计得真巧妙说白了就是用一个“人为制造的间距”来抵消“未知长度”带来的麻烦。3.1 核心思路既然我们要删除倒数第 n 个结点等价于找到一个位置它距离链表末尾正好 n 步。我们可以在链表头部设置两个指针 fast 和 slow先让 fast 前进 n 步这样 fast 和 slow 之间就差 n 个结点。随后再让 fast 和 slow 以相同速度前进每次各走一步。当 fast 到达链表末尾的 null 时slow 正好停在倒数第 n 个结点上。但你马上会发现一个细节我们要删除的是倒数第 n 个结点而删除操作需要前驱结点。如果 slow 正好指向目标结点本身我们还需要额外记录它前一个结点是谁。这可以有两种处理方案用另一个指针 preSlow 始终记录 slow 的前一个位置。更常见的做法是让 fast 先走 n 1 步这样当 fast 走到 null 时slow 正好停在目标结点的前驱位置。我推荐第二种因为省代码、理解起来也顺。但要记住使用第二种方案时我们需要保证 fast 在走 n 1 步时不越界而绝大多数题目会保证 n 不超过链表长度因此 fast 可以先走 n 步再判断是不是 null决定是否追加一步。3.2 标准代码实现下面是 Java 版本的快慢指针解法。为了统一处理“删除头结点”这种边界我引入了一个虚拟头结点 dummy。这个技巧在链表删除类题目中很常见值得单独说一说。public ListNode removeNthFromEnd(ListNode head, int n) { // 虚拟头结点避免单独处理“删除头结点”的逻辑分支 ListNode dummy new ListNode(0); dummy.next head; ListNode fast dummy; ListNode slow dummy; // 先让 fast 走 n 1 步 for (int i 0; i n; i) { fast fast.next; } // 再让 fast 和 slow 同步前进 while (fast ! null) { fast fast.next; slow slow.next; } // 此时 slow.next 就是待删除的结点 slow.next slow.next.next; // 返回虚拟头结点的 next也就是真正的头结点 return dummy.next; }只是实际写代码的时候还有个问题如果链表长度正好等于 n那 fast 先走 n 步就已经指向 null再走第 n 1 步就会空指针。所以更稳健的写法是分两步走public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy new ListNode(0); dummy.next head; ListNode fast dummy; ListNode slow dummy; // 第一步fast 先走 n 步 for (int i 0; i n; i) { fast fast.next; } // 第二步fast 再走一步如果 fast 已经是 null说明 n 等于链表长度 // 要删的是头结点此时 slow 保持不动即可 if (fast.next ! null) { fast fast.next; } // 同步前进 while (fast ! null) { fast fast.next; slow slow.next; } slow.next slow.next.next; return dummy.next; }3.3 为什么快慢指针能一次遍历解决问题关键在于 fast 提前走出的“距离差”代替了“计算链表长度”的过程。我们不需要知道链表总量有多少只需要让 fast 和 slow 之间永远保持 n 步的间距然后一起走到终点。这个过程里fast 和 slow 加起来总共也只遍历了一次链表因为 fast 在前面开路slow 被动跟进二者不会重复走同一段路。这个思路的生活化类比是你和一个朋友在跑道上跑步你先让他跑出一段固定距离比如 10 米然后你们俩速度相同地同时往前跑。当朋友到达终点时你距离终点正好是那 10 米。那道题里这个“10 米”就是 n 个结点而你所在的位置就是倒数第 n 个结点。4. 边界条件与哑结点技巧链表题和数组题最大的区别之一就是链表题的边界情况特别多且特别容易导致代码崩溃。数组越界会抛异常链表操作错了往往直接出现环或者丢结点调试起来非常痛苦。所以每次写完链表代码我都会先跑一遍边界用例再提交。这段我把这道题里所有值得注意的边界情况全部列出来并给出处理建议。4.1 删除头结点的情况当 n 等于链表长度时倒数第 n 个结点就是头结点。如果你不使用虚拟头结点那么删除头结点的操作需要特判直接将 head 指向 head.next。很多初学版本的代码里一旦忘记这个特判就会出现一个诡异的现象删除倒数第 n 个结点后链表前段被丢掉了。我当时第一次写两次遍历法时就是在这个地方错的。原因是循环计算前驱位置时length - n 等于 0前驱从 head 开始走 0 步得到的 pre 还是头结点然后执行 pre.next pre.next.next结果把第二个结点给删了头结点反而没动。这种情况不好排查因为链表长度如果是 5删除倒数第 5 个结点正常结果应该是删掉第一个结点而我却删掉了第二个。这种情况后来我改成用哑结点统一处理就再也不需要考虑这种偏置问题了。4.2 哑结点为什么能统一逻辑哑结点是人为在头结点之前增加的一个额外结点值为多少无所谓关键在于它给链表补了一个“虚拟前驱”。有了它删除头结点这件事就从“单独处理 head”变成了“正常处理一个普通结点”因为头结点的前驱已经由 dummy 充当了。使用哑结点的框架大致是这样创建 dummydummy.next head。所有指针初始化都从 dummy 开始而不是从 head 开始。最终返回 dummy.next而不是 head。这样做还有个好处即使原 head 被删除了dummy.next 也已经自动指向新的头结点。这套处理方式在“删除指定结点”“合并两个链表”等很多链表题里都通用。学会了以后你能省下大量处理边界的精力。4.3 链表只有一个结点时会发生什么如果链表只有一个结点n 1这意味着要删除这个唯一的结点。删除之后链表应该变为空。使用哑结点方案时fast 先走 n 1 步由于 dummy 是虚拟头fast 走到原 head 结点然后判断 fast.next此时 fast.next 为 null因此跳过额外的一步进入 while (fast ! null)。由于 fast 不为 null它指向原 headslow 和 fast 各走一步fast 从原 head 移动到 nullslow 从 dummy 移动到 head 结点。最后执行 slow.next slow.next.next也就是 head.next null因为 head.next 本来就是 null所以链表收缩为空返回 dummy.next 为 null。整个过程不会出现空指针异常。如果不使用哑结点这个问题会变得更敏感slow 初始化指向 headfast 往后再走很容易出现 slow 为 null 或者 fast 为 null 的混乱状态。这就是强烈推荐哑结点的原因。4.4 n 不合法时的处理策略通常题目会限制 n 的范围确保 1 n 链表长度。但面试时最好主动和面试官确认一下如果 n 超出了这个范围应该怎么处理。有些版本会直接返回 null有些会选择抛异常有些则忽略非法输入。严格来说这不是算法题本身的核心矛盾所以多数刷题站点不会把它设计成隐藏测试用例。但你写工程代码时不能假设输入一定合法至少要在函数入口做防御性判断。写法和意图都清晰同时不会干扰正常逻辑。5. 复杂度分析与两种解法对比到了这一节我们可以站在更高的维度审视一下两种做法。面试中讲完代码之后面试官几乎必然会追问时间复杂度和空间复杂度因此提前把这个讲清楚很有必要。5.1 时间复杂度的准确测算两次遍历法的时间开销由两部分组成第一次遍历完整链表计算出长度 L访问次数为 L。第二次遍历到目标结点的前驱最多访问 L 次。所以总访问次数大约是 2L 量级时间复杂度记作 O(L)。快慢指针法需要 fast 从 dummy 出发走 n 步建立间距然后 fast 和 slow 同步前进。fast 实际走过的结点数大约为 L 1slow 走过的结点数也在这个范围内两者总访问次数接近 2L。因此从严格意义上说快慢指针法的时间复杂度同样是 O(L)只是它省去了“第一次完整遍历”的独立环节把两次遍历合成了一趟。在很多刷题教程里会直接说“快慢指针法只遍历一次”这里要澄清一下从语义上是“一次遍历”从访问次数上是“仍然需要走到链表末尾”但确实比两次独立的遍历更简洁。也有一种优化思路是从头结点开始先让 fast 走 n 步然后再同时出发这样 fast 的访问次数大约为 L - n 1slow 的访问次数也大致如此总访问次数会略小于 2L。但代码实现上对边界的处理会更麻烦我权衡之后还是推荐从 dummy 出发的标准写法稳定性优先。5.2 空间复杂度分析两种方案都不需要额外的链表存储空间只使用了若干个指针变量所以空间复杂度都是 O(1)。这里要注意Java 里的 ListNode 对象本身是题目给出的不算入我们额外申请的空间。如果你在解题过程中创建了额外的数组来存放结点引用那空间复杂度就会变成 O(L)面试时很容易被扣分。5.3 两种方案的适用场景简单总结来说方案时间复杂度空间复杂度代码难度边界处理适用场景两次遍历O(L)O(1)低需要单独处理头结点日常工作、快速 AC快慢指针O(L)O(1)中配合哑结点更稳面试展示、单次遍历需求递归回溯O(L)O(L)中高依赖栈空间练习递归思想不推荐用于面试关于递归方案我简单提一句可以通过递归返回到当前层的“位置信息”来判断当前结点是否为倒数第 n 个。思路很巧妙但由于递归深度等于链表长度空间复杂度是 O(L)在链表很长时可能爆栈所以不管是面试还是工程实践都不如两个 O(1) 空间方案好用。6. 常见错误与现场排查实录这里整理的是我刷这道题和给其他人 review 代码时遇到过的高频问题。每一个都是真实踩过的坑不是理论推演。6.1 空指针异常症状程序一运行就抛 NullPointerException位置在 fast.next 或 slow.next 附近。原因分析最常见的是 fast 先走 n 1 步时链表长度本身就只有 n 个结点fast 在第 n 步之后已经指向 null再访问 fast.next 直接就崩。有一种解法直接写 for (int i 0; i n; i)却忽略了 n 恰好等于 length 时 fast 会变成 null 这一点。排查方法在 fast 走完第一步和第二步之间加一个条件判断if (fast.next ! null)。如果 fast.next 是 null说明 fast 已经是尾结点此时 fast 不能再向前走了直接进入同步阶段即可。另外哑结点的存在也能减少指针为 null 的概率因为 slow 初始从 dummy 出发不会在一开始就指向真实头结点。6.2 删掉的结点不对症状链表没报错返回结果也正常但被删除的结点位置偏了一位比如删了倒数第 n 1 个结点。原因分析这几乎都是“间距”没有调整正确导致的。fast 先走 n 步的话最后 slow 指向的是目标结点的前驱而不是目标结点本身。如果循环里写成 i n 而不是 i n或者多走了一步的时候判断没做好slow 的停位就会偏差。排查方法把自己代入最极端的例子。假设链表只有 3 个结点n 1也就是删除最后一个结点。手动跑一遍fast 从 dummy 出发先走 1 步到达结点 1因为 fast.next 不是 null是结点 2fast 再走 1 步到达结点 2。随后 fast 和 slow 同步前进fast 从结点 2 走到结点 3 再走到 nullslow 从 dummy 走到结点 1。此时 slow.next 是结点 2也就是我们要删除的倒数第 1 个结点而实际的倒数第 1 个结点明明是结点 3。这就发现间距错了正确的做法是 fast 先走 n 1 步。这个例子是最容易定位问题的我建议每个遇到这类 bug 的人都亲手走一遍。6.3 头结点被吞掉症状删除操作执行后链表从第二个结点开始原来的头结点没了。原因分析这种情况多半发生在没有使用哑结点、且删除目标就是头结点的时候。因为 slow 初始指向 head如果 n 等于链表长度slow 经过若干步后停在了头结点然后执行 slow.next slow.next.next相当于删除了第二个结点而头结点没有变化。再细看返回结果是 head但 head 没被删。看起来好像是“链表丢了一个结点”实际上是把第二个结点误删了。排查方法优先使用哑结点方案。如果坚持不用哑结点那就在循环前判断 n length并将 head 指向 head.next。6.4 返回值写错症状逻辑全对但最终 return 的是原 head而原 head 恰好已经被删了。原因分析这个错误常常出现在脑子已经混乱的复盘环节。使用哑结点时如果返回 head而 head 已经被删除实际上返回的是一个没有被链表引用的孤立结点虽然它的 next 还能连到后面的结点但它本身不应再作为链表头。正确做法永远返回 dummy.next。在未删除头结点时dummy.next 就是原 head在删除头结点后dummy.next 自动更新为新头结点。6.5 调试技巧用打印法快速定位我会在关键位置打印当前指针指向的结点值比如每次循环开始时打印 fast.val 和 slow.val。虽然刷题平台上会限制输出格式但在本地调试时这招非常管用。举例来说输入链表 1 - 2 - 3 - 4 - 5n 2我在快慢指针同步阶段看到的输出应该是fast2, slow0 fast3, slow1 fast4, slow2 fast5, slow3 fastnull, slow4这个最后一行很关键当 fast 为 null 时slow 停在结点 4而倒数第 2 个结点是结点 4不对倒数第 2 个结点应该是 4这里我故意留个坑让你自己跑一遍。实际上链表 1 到 5 的倒数第 2 个结点是 4按理说 slow 应该停在 4 的前驱即结点 3。正确打印应当是最后一行 slow3。如果打印结果显示 slow4说明 fast 先走的步数太多或太少间距偏了。7. 扩展思考与实战建议这道题能延展出的点其实不少我整理了一些值得深入的方向适合刷完题之后再做一点思维体操。7.1 变形一删除倒数第 N 个结点并返回头结点这是标准版本本文已经详细讨论。重点注意哑结点的使用。7.2 变形二找到链表的中间结点这道题同样可以用快慢指针不过速度不同快指针一次走两步慢指针一次走一步。当快指针到达末尾时慢指针停在中间位置。它跟路径可复用先走 n 步建立间距再同步前进。7.3 变形三判断链表是否有环快慢指针的经典应用。快指针每次走两步慢指针每次走一步如果存在环两者最终会相遇。这类题和删除倒数第 N 个结点共享同一个思想工具库但边界条件差异很大建议放在一起刷。7.4 变形四删除链表中所有值等于目标值的结点去掉“倒数第 N 个”的限制改为按值删除。此时同样强烈推荐哑结点因为头结点本身就可能需要被删除。这道题可以很好地检验你是否真的理解“删除依赖前驱”这一约束。我个人的经验是把这几道链表题放在一起对照着刷复习效率比孤立刷单题高很多。7.5 手写代码时的习惯建议统一用 dummy 结点处理链表删除类问题能省一半的边界思考。写完代码后先跑空链表、单结点链表、删除头结点、删除尾结点这四类用例。尽可能抽一个独立函数用于创建链表和打印链表方便本地调试。面试时先在白板上画链表示意图把指针移动路径画出来再动手写代码。画图的过程本身就是在做边界验证。8. 最后的几点个人体会刷了这么多年算法题链表题一直是我觉得“看起来简单、写起来容易翻车”的类型。最近一次复习这道题时我又重新把两种解法写了一遍发现即使已经写过很多遍如果不集中精力边界条件依然可能出错。所以如果你想彻底掌握这道题光靠看文章是不够的必须自己动手在编辑器里敲一遍再打断点调试一遍最后再默写一遍。三遍下来你对单链表结构的感觉会明显不一样。还有一个小技巧做链表题时无论题目是什么先画图。我见过太多人拿到题就开始写代码写一半卡住了才发现自己搞错了指针方向。画图最多花两分钟但它能帮你省下二十分钟的调试时间。用箭头表示指针用方框表示结点把每一步变化都标注出来尤其在处理快慢指针时特别有效。这道题不是最难的链表题但它正好卡在“基础”和“技巧”的分界线上没有刁钻的数学推导也没有复杂的递归设计需要的只是你对链表结构本身的熟悉程度和对边界条件的敏锐性。把这题吃透后续再碰链表的反转、合并、排序、去重等问题会顺手很多。至少对我来说快慢指针这个解题工具就是从那段时间的反复练习里真正长在脑子里的。