【Java实习面试算法冲刺】链表

第4类题型：链表

为什么链表题你感觉思路不难，一写代码却总把链断掉

很多同学刷链表题时，第一反应都是“这题思想不难，就是操作麻烦”。这句话只说对了一半。链表题真正拉开差距的地方，不是你知不知道反转、删除、判环这些套路，而是你能不能在每一步指针修改时都保持清醒。

这类题最容易暴露出几种典型问题：

• 你知道要改next，但一改就把后续节点丢了。
• 你会写删除节点，却没提前想到头结点可能变化。
• 你记住了快慢指针模板，但说不清为什么这样走一定能找到答案。

1. 核心知识点

链表题的难点通常不是算法思想多复杂，而是指针操作顺序很容易错。你必须先养成两个习惯：

• 改指针之前先保存next。
• 遇到头结点可能变化的问题，优先考虑虚拟头结点dummy。

链表高频模型主要有：

• 反转链表。
• 合并链表。
• 快慢指针。
• 删除节点。
• 判环。

其中最核心的 3 个模板是：

反转链表

ListNodeprev=null;ListNodecurr=head;while(curr!=null){ListNodenext=curr.next;curr.next=prev;prev=curr;curr=next;}returnprev;

虚拟头结点

ListNodedummy=newListNode(0,head);

快慢指针

ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;}

动画辅助理解：改指针前先保存后继

链表题最适合用206. 反转链表建立第一印象。你可以先打开本地动画页：

链表：反转链表分步动画

这个动画最值得盯住的是 4 步：

• 先明确当前要处理的节点是cur，已经反转好的部分头结点是prev。
• 改cur.next之前，必须先把原来的后继保存到next。
• 再执行cur.next = prev，完成一个节点的局部反转。
• 最后整体推进prev = cur、cur = next，继续处理下一段链。

拿1 -> 2 -> 3 -> null举例，状态变化可以这样记：

2. 这类题在面试里考什么

链表题常见，但能非常直接地看出候选人是否稳。

面试官在看：

• 你是否清楚每个指针当前指向谁。
• 你会不会因为修改顺序错误而把链断掉。
• 你是否知道什么时候该加dummy。
• 你是否理解快慢指针的语义，而不只是机械套模板。

很多候选人链表题不是败在思路，而是败在“指针含义没说清、边界没提前想”。所以链表题的区分度，往往就在这些细节上。

3. 高频题清单

4. 这类题最容易犯的 3 个错误

1. 指针还没保存next就直接改链，结果后续节点丢了。
2. 头结点可能变化的题，不加dummy，边界写得很乱。
3. 快慢指针会背，但说不清为什么快指针先走n步。

5. 代表题精讲 1

题目

206. 反转链表

思路

这题是链表基本功。核心在于把当前节点的next指向前一个节点，所以每次循环都要做 4 件事：

1. 先保存curr.next。
2. 再改curr.next = prev。
3. prev前进到curr。
4. curr前进到原来的next。

Java 代码

classSolution{publicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecurr=head;while(curr!=null){ListNodenext=curr.next;curr.next=prev;prev=curr;curr=next;}returnprev;}}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

边界提醒

这题最容易漏想的边界其实不复杂：空链表和只有一个节点的链表。好消息是这套写法天然就能覆盖，因为curr == null时循环根本不会进入；只有一个节点时，执行一轮之后也会正确返回它自己。

如果这是面试现场，你可以这样说

这题本质上是逐个节点把指针方向反过来。为了不丢链，我会先保存当前节点的下一个节点，再把当前节点的next指向前驱节点。prev表示已经反转好的部分头结点，curr表示当前要处理的节点。整个过程只需要一次遍历。

6. 代表题精讲 2

题目

19. 删除链表的倒数第 N 个结点

思路

这是快慢指针和dummy的组合题。

为什么要加dummy：因为被删除的节点可能正好是原头结点。

为什么快指针先走n步：这样当快指针走到链表末尾时，慢指针刚好停在“待删除节点的前一个节点”，方便删除。

做法：

1. 建dummy -> head。
2. fast先走n步。
3. slow从dummy出发，与fast一起走，直到fast.next == null。
4. 此时slow.next就是待删除节点，执行删除。

Java 代码

classSolution{publicListNoderemoveNthFromEnd(ListNodehead,intn){ListNodedummy=newListNode(0,head);ListNodefast=dummy;ListNodeslow=dummy;for(inti=0;i<n;i++){fast=fast.next;}while(fast.next!=null){fast=fast.next;slow=slow.next;}slow.next=slow.next.next;returndummy.next;}}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

边界提醒

这里最关键的边界不是代码长短，而是“删除的可能就是原头结点”。比如链表是1 -> 2 -> 3，n = 3，真正要删的是第一个节点。如果你没有先建dummy，就得单独处理头结点变化；而加了dummy之后，这个边界会自动归入统一流程。

如果这是面试现场，你可以这样说

这题我会用虚拟头结点加快慢指针。先让快指针走n步，这样快慢指针之间就保持了固定距离。之后它们一起走，当快指针到达尾部时，慢指针刚好停在待删除节点的前一个位置。用dummy可以统一处理删除头结点的边界。

7. 其余题模板与关键片段

21. 合并两个有序链表

用dummy串起来：

ListNodedummy=newListNode(0);ListNodetail=dummy;while(list1!=null&&list2!=null){if(list1.val<=list2.val){tail.next=list1;list1=list1.next;}else{tail.next=list2;list2=list2.next;}tail=tail.next;}tail.next=(list1!=null)?list1:list2;

这类题的核心不是“会不会连”，而是你能不能保证tail始终指向已经合并好部分的最后一个节点。只要这个语义稳定，代码就不容易乱。

141. 环形链表

Floyd 判环：

while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){returntrue;}}returnfalse;

为什么它成立：如果有环，快指针每次比慢指针多走一步，它们进入环之后，距离会不断缩短，最终一定会在环里相遇；如果无环，快指针会先走到null。

8. 链表题先判断什么

真正写代码前，你可以先问自己 4 个问题：

1. 这题会不会改动头结点。
2. 我现在改next之前，后继节点有没有保存。
3. 这题更像反转 / 删除 / 合并，还是快慢指针问题。
4. 我当前每个指针的语义能不能用一句话说清。

这 4 个问题回答清楚，链表题大部分错误都能提前拦下来。

9. 错题本记录方式

链表题建议重点记：

• 我是在哪一步把链断掉的。
• 这题头结点会不会变化，是否应该先加dummy。
• 快慢指针里，slow和fast分别表示什么。
• 删除、反转、合并时，哪一步最容易顺序写错。

10. 面试前 3 分钟速记

• 改链前先保存next。
• 头结点可能变化，优先想dummy。
• 反转链表记住prev / curr / next。
• 删除倒数第 N 个结点记住：dummy + fast先走n步。
• 判环记住：slow走1步，fast走2步。

11. 最后总结：链表题的核心不是模板，而是指针语义别乱

如果你只能记住一句话，那就是：链表题真正难的地方不是模板多，而是你必须始终知道“当前这几个指针分别指向谁”。

面试时你可以按这个顺序去讲：

1. 这题头结点会不会变化，要不要先上dummy。
2. 我当前维护的每个指针分别表示什么。
3. 我改next之前，是否已经把后继保存好了。
4. 这题的答案是返回prev、dummy.next，还是某个相遇节点。

这样你写出来的链表代码会稳定很多，也更容易把思路讲清楚。

上期速递：【Java实习面试算法冲刺】滑动窗口

下一篇：正在路上……
感谢阅读，记得点赞、关注、收藏，欢迎各位评论区交流！！！