链表删除最怕丢前驱：从一次代码审查看哨兵节点h

链表删除最怕丢前驱：从一次代码审查看哨兵节点

摘要：CSDN 算法频道里链表题的讨论热度不低，原因很直接：链表代码短，却特别容易在删除头结点、连续删除、区间反转时写出空指针或丢链问题。本文用“代码审查”的方式复盘两个高频操作，给出一份 Java 11 可运行实现，并把哨兵节点的价值讲透。

链表题最迷惑人的地方是：看上去只要移动几个 next 指针，真正出错时却很难从栈信息里看出原因。数组越界通常很醒目，链表丢了一段节点却可能只表现为结果少了几个数，甚至本地样例全过，边界用例一来就崩。

这次我们假设正在审查一段“删除指定值节点”的代码。常见初稿是：如果当前节点值等于 target，就让当前节点跳到下一个；否则继续走。听起来没错，但马上会遇到第一个问题：如果要删的是头结点，谁来修改 head？第二个问题更隐蔽：如果连续两个节点都要删除，prev 指针要不要移动？第三个问题出现在区间反转：left 等于 1 时，反转后的新头结点从哪里返回？

审查点一：让所有节点都有前驱

哨兵节点 dummy 的目的不是“多写一行模板”，而是把头结点也变成普通节点。原链表 head 前面人为接一个值无意义的节点，删除、插入、反转都从 dummy.next 开始。这样一来，删除头结点和删除中间节点是同一种操作：prev.next = cur.next。

更重要的是，哨兵节点让返回值稳定。无论原来的 head 是否被删掉，最后都返回 dummy.next。这个小技巧可以让很多链表题少掉一半特殊分支。

审查点二：删除时 prev 不一定前进

删除当前节点后，prev 不能动，因为 prev.next 已经指向了新的 cur。如果此时 prev 也前进，就会跳过连续 target。例如链表 5 -> 5 -> 5，删除第一个 5 后，prev 仍应停在 dummy，继续检查新的 dummy.next。

保留这个不变量：prev 永远指向“已经确认保留的尾节点”，cur 指向“正在审查的节点”。只有 cur 被保留时，prev 才能移动到 cur。

审查点三：区间反转不需要真的找尾巴

反转 left 到 right 的区间，可以使用头插法。先找到区间前一个节点 before，再记住 segmentHead，也就是反转段原本的第一个节点。每轮把 segmentHead 后面的节点摘出来，插到 before 后面。这样 right - left 轮之后，区间自然反转，segmentHead 会变成这段的尾巴。

一份可执行的审查清单

审查链表代码时，我会先看返回值，再看循环不变量，最后看测试覆盖。返回值决定头结点被修改后能否传出去；循环不变量决定 prev、cur、next 三个指针是否各司其职；测试覆盖决定边界是否真正走过。很多链表错误不是算法想错，而是“当前节点被删后，下一轮从哪里开始”没有写成稳定规则。

以删除节点为例，审查时可以逐行追问：cur 指向的节点如果保留，prev 是否移动；cur 指向的节点如果删除，prev 是否停住；删除最后一个节点时 prev.next 是否会变成 null；全链表都被删除时 dummy.next 是否为空。只要这四个问题都能用同一套代码回答，基本不会出现头结点特判和中间节点逻辑打架的情况。

区间反转则要抓住两个节点：before 和 segmentHead。before 永远站在反转段前面，segmentHead 永远是反转段当前尾巴。每次移动的 moved 都来自 segmentHead.next，被摘下后插到 before.next。这样你不需要在脑子里同时维护整段链表，只要确认三条边：segmentHead.next 接上 moved 后面，moved.next 接上当前段头，before.next 改成 moved。指针题最怕“凭感觉改两条边”，最好每次都数清楚改了哪三条。

为什么不用递归写

链表反转也可以递归写，代码看起来更短。但在面试和业务代码里，递归有两个额外问题：一是调用栈深度受输入规模影响，长链表可能栈溢出；二是删除和区间反转混在一起时，递归返回值更难审查。本文选择迭代写法，是为了让每一步指针变化都能被打印、断点和测试观察到。

如果题目要求“每 k 个一组反转”，也可以复用同样的思路。先找到每组 before，再确认这一组长度足够，随后用头插法做 k - 1 次移动。也就是说，哨兵节点不是只服务于某一道题，而是一种把头部边界统一进普通流程的建模方式。

下面是完整实现，包含删除、区间反转和断言测试。

classLinkedListReview{staticclassNode{intval;Nodenext;Node(intval){this.val=val;}}staticNodebuild(int...values){Nodedummy=newNode(0);Nodetail=dummy;for(intv:values){tail.next=newNode(v);tail=tail.next;}returndummy.next;}staticStringasText(Nodehead){StringBuildersb=newStringBuilder("[");while(head!=null){if(sb.length()>1)sb.append(", ");sb.append(head.val);head=head.next;}returnsb.append("]").toString();}staticNodeeraseAll(Nodehead,inttarget){Nodedummy=newNode(0);dummy.next=head;Nodeprev=dummy;Nodecur=head;while(cur!=null){if(cur.val==target){prev.next=cur.next;cur=cur.next;}else{prev=cur;cur=cur.next;}}returndummy.next;}staticNodereverseBetween(Nodehead,intleft,intright){if(head==null||left>=right)returnhead;Nodedummy=newNode(0);dummy.next=head;Nodebefore=dummy;for(inti=1;i<left&&before.next!=null;i++){before=before.next;}NodesegmentHead=before.next;if(segmentHead==null)returndummy.next;for(inti=0;i<right-left&&segmentHead.next!=null;i++){Nodemoved=segmentHead.next;segmentHead.next=moved.next;moved.next=before.next;before.next=moved;}returndummy.next;}staticvoidexpect(Nodehead,Stringwanted){Stringactual=asText(head);if(!actual.equals(wanted)){thrownewAssertionError("expected "+wanted+", got "+actual);}System.out.println("ok "+actual);}publicstaticvoidmain(String[]args){expect(eraseAll(build(1,2,6,3,6,4,6),6),"[1, 2, 3, 4]");expect(eraseAll(build(5,5,5),5),"[]");expect(reverseBetween(build(1,2,3,4,5),2,4),"[1, 4, 3, 2, 5]");expect(reverseBetween(build(1),1,1),"[1]");}}

本地运行结果：

ok [1, 2, 3, 4] ok [] ok [1, 4, 3, 2, 5] ok [1]

复杂度分析

删除所有 target 需要线性扫描一次，时间复杂度 O(n)，额外空间 O(1)。区间反转只移动 right - left 次节点，最坏情况下仍是 O(n)，额外空间 O(1)。这里没有创建新链表，所有操作都在原节点上重连 next 指针。

边界条件

• 空链表直接返回空。
• 删除值出现在头部、尾部、连续多次出现，都必须覆盖。
• left 等于 right 时不需要反转。
• right 超过链表长度时，本文实现会尽量反转到尾部；如果题目要求非法输入报错，可以在进入反转前先检查长度。
• Java 里不需要手动释放节点，但 C++ 实现要注意删除节点后的悬空指针。

在把链表操作封装成在线练习服务、批量判题器或接口化原型时，建议把随机用例生成、结果对拍和超时限制拆开；如果还要接入模型辅助审题或生成测试说明，https://haerapi.com 可以作为开发者自行评估的 API 接入选项之一，但链表判题本身仍应依赖确定性测试。

常见错误

第一，删除头结点时忘记更新 head。第二，删除当前节点后仍然移动 prev，导致连续目标值漏删。第三，区间反转时先改断 segmentHead.next，却没有保存 moved.next，造成后半段丢失。第四，把 dummy 当成真实节点输出，结果多了一个 0。第五，只测普通样例，不测空链表、单节点和全删光。

可复制测试用例

建议至少保留四组：1 -> 2 -> 6 -> 3 -> 6 -> 4 -> 6 删除 6，结果应为 1 -> 2 -> 3 -> 4；5 -> 5 -> 5 删除 5，结果为空；1 -> 2 -> 3 -> 4 -> 5 反转 2 到 4，结果为 1 -> 4 -> 3 -> 2 -> 5；单节点反转 1 到 1，结果不变。

总结

链表题不是拼手速，而是维护指针不变量。哨兵节点把头结点纳入普通流程，prev 表示已确认保留的尾节点，区间反转用头插法减少分支。把这三个点写清楚，删除和反转就不再依赖运气。