链表删除最怕丢前驱从一次代码审查看哨兵节点摘要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.valval;}}staticNodebuild(int...values){NodedummynewNode(0);Nodetaildummy;for(intv:values){tail.nextnewNode(v);tailtail.next;}returndummy.next;}staticStringasText(Nodehead){StringBuildersbnewStringBuilder([);while(head!null){if(sb.length()1)sb.append(, );sb.append(head.val);headhead.next;}returnsb.append(]).toString();}staticNodeeraseAll(Nodehead,inttarget){NodedummynewNode(0);dummy.nexthead;Nodeprevdummy;Nodecurhead;while(cur!null){if(cur.valtarget){prev.nextcur.next;curcur.next;}else{prevcur;curcur.next;}}returndummy.next;}staticNodereverseBetween(Nodehead,intleft,intright){if(headnull||leftright)returnhead;NodedummynewNode(0);dummy.nexthead;Nodebeforedummy;for(inti1;ileftbefore.next!null;i){beforebefore.next;}NodesegmentHeadbefore.next;if(segmentHeadnull)returndummy.next;for(inti0;iright-leftsegmentHead.next!null;i){NodemovedsegmentHead.next;segmentHead.nextmoved.next;moved.nextbefore.next;before.nextmoved;}returndummy.next;}staticvoidexpect(Nodehead,Stringwanted){StringactualasText(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 - 45 - 5 - 5 删除 5结果为空1 - 2 - 3 - 4 - 5 反转 2 到 4结果为 1 - 4 - 3 - 2 - 5单节点反转 1 到 1结果不变。总结链表题不是拼手速而是维护指针不变量。哨兵节点把头结点纳入普通流程prev 表示已确认保留的尾节点区间反转用头插法减少分支。把这三个点写清楚删除和反转就不再依赖运气。
