链表这块内容大学里第一次接触的时候觉得简单无非是节点加指针。可真到动手写题的时候删除节点能删丢一半反转链表能绕成环找中间节点还会因为奇偶数量吵半天。单链表综合练习里的“删除指定值节点”“反转链表”“找中间节点”这三题几乎就是所有链表题的地基。这篇就把它们拆开揉碎过一遍把解题思路、边界处理和踩坑经验一起讲清楚适合正在学数据结构的学生也适合准备算法面试想快速过一遍链表基础的人只要你懂节点的next指针是干什么的就能跟下来。1. 三个题目放在一起练到底能学到什么1.1 单链表先过一遍节点是怎么串起来的单链表的结构特别直白每个节点存一个数据外加一个指向下一个节点的指针最后一个节点的指针指向空。我们用C定义一下就是这样struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };它像什么像小时候玩的寻宝游戏每张纸条上写着一条线索还写着下一条线索藏在哪里。你只能顺着纸条一张张找下去想回头找上一条不好意思没有回头路。这就是链表最核心的特点单向、不可回退、不支持随机访问。你想拿到第5个节点必须从第1个节点一步步走过去没有“下标”可以直接跳。很多初学者会拿它跟数组比较。数组是一排连续的柜子你知道第5个柜子在哪就能直接走到链表是一串散落的纸条每张只记着下一张的线索。这个差别决定了链表几乎所有算法的思考方式想对链表做任何操作基本都逃不开“从头遍历”和“维护指针之间的关系”。1.2 三个题的内在联系都是指针操作但考察点不同这三道题看起来各做各的实际上一脉相承都在练同一种核心能力在遍历过程中正确地调整指针。删除指定值节点考的是“前驱指针”的概念。因为链表删除的本质不是抹掉节点而是让前一个节点的指针跳过当前节点直接指向后一个节点。要完成这一步你必须始终记住当前节点的前驱是谁。反转链表考的是“指针方向重定向”。原来每个节点都指向下一个节点反转之后每个节点要指向前一个节点。这条指针链要全部反过来稍不留神就会断掉。找链表中间节点考的是“快慢指针”的思路。一快一慢两个指针同时走快的走两步慢的走一步快的到终点时慢的正好在中间。它不涉及前驱也不涉及反转但它锻炼的是双指针配合的节奏感。用一个表格把三道题的考察点拎出来会更清晰题目核心难点关键技巧常用复杂度删除指定值节点删除头节点时谁来做前驱哑节点法统一逻辑O(n)时间O(1)空间反转链表防止断链、指针反向先保存下一个节点再改指向O(n)时间O(1)空间找中间节点奇偶数量决定中间点位置快慢指针一趟遍历O(n)时间O(1)空间所以别把这三题当成孤立的小练习。它们就像是单链表操作里的“绑腿跑”每个都让你对指针的流动更敏感练完以后再碰到“删除倒数第N个节点”“回文链表”这类组合题你会发现那些变体只是把这三个基本功重新排列组合。1.3 练习方式和语言选型刷这个练习语言不是重点重点是你要能亲眼看见指针的变化。我个人推荐先用C/C写一遍因为它用真正的指针节点之间的关系看得见摸得着写错了会直接编译或崩溃给你看。Java和Python里虽然叫“引用”底层逻辑是一样的只是隐藏了一些细节。用哪种语言都不影响理解只要你愿意手动画图。实际操作中我的建议是先把每个题的示意图画出来标出每一步指针的位置。再在编辑器里敲代码不要直接背模板。自己准备几个小用例跑一遍比如空链表只有一个节点删除头节点连续重复值等。在手机上用在线编译器或者电脑本地IDE都行重点是能快速改、快速跑。2. 删除链表中等于给定值 val 的所有节点关键是处理头节点2.1 先别急着写代码把删除操作拆明白这道题要求把链表中所有值等于val的节点都删掉不是只删第一个。先想清楚删除一个普通节点的动作假设当前节点是cur它的前驱是prev那删除cur只需要一行prev-next cur-next;这句话的意思是让前驱节点越过cur直接连到cur的下一个节点。链表的结构让它天然支持这种操作不需要移动内存比数组的删除高效得多。问题来了。如果cur正好是头节点它没有前驱怎么执行上面那句话很多新手第一版代码里会写一堆特判先while循环把头节点中所有等于val的删掉再处理后面的。这样能跑但是一长串if、else相当容易漏尤其是当头节点连续好几个都等于val时特判会把自己绕晕。解决办法有两个方向一个是在删除头节点时单独维护head head-next一个是用一个哑节点dummy node把头节点变成普通节点。后者思路清奇但写起来极稳也是实际编码里我最推荐的方式。2.2 哑节点写法逻辑统一不特判哑节点的想法很简单手动创建一个不存储实际数据的节点把它放在链表头之前让它的next指向原链表的头节点。这样一来原链表的头节点也有“前驱”了所有删除操作都能用同一套逻辑处理。ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; ListNode* cur head; while (cur) { if (cur-val val) { prev-next cur-next; cur cur-next; } else { prev cur; cur cur-next; } } ListNode* newHead dummy-next; delete dummy; return newHead; }你看整个循环里只有两种情况当前节点要删那就让prev-next跳过它当前节点不删那就把prev更新成当前节点。无论删除的是头节点、中间节点还是尾节点代码完全不用变。这一步的关键是理解为什么prev移动要分情况因为如果删除了当前节点prev不该跟着往后走它要继续指向最新保留下来的前驱不然下一个节点如果也要删就会漏掉。如果不删除prev才应该移动到当前节点。很多人第一次写会直接把prev放在循环外每次都后移结果重复节点删不干净就是这个原因。提示C里如果用new创建了节点记得手动delete。在线编译平台一般不销毁也没事但养成释放内存的习惯总没坏处。2.3 递归解法和双指针写法两种思路作为对比除了哑节点这题还有两种常见写法。第一种是不建哑节点直接用两个指针迭代。prev初始化为null循环里如果cur-val val那就分两种情况如果prev为null说明要删的是头节点直接把head往后挪如果prev不为null执行prev-next cur-next。这种写法同样能过但每删一次头节点都要判断一次代码比哑节点版本啰嗦也更容易漏逻辑。第二种是递归写法代码极其简洁ListNode* removeElements(ListNode* head, int val) { if (!head) return nullptr; head-next removeElements(head-next, val); return head-val val ? head-next : head; }递归的思路是“我先把后面的链表处理好再回头处理当前节点”。每一步都先递归处理子链表返回的结果是一个已经删干净且不含val的链表然后判断当前节点要不要被删。三行代码看着爽但有一个隐藏问题递归深度等于链表长度链表特别长的时候可能栈溢出工程里不太推荐。两种方式对比下来哑节点迭代法是原理直观、代码稳定、空间O(1)的最优选。递归适合用来加深理解不建议在实际代码里面无脑用。2.4 边界条件与常见坑连续重复值和内存释放这道题最容易翻车的地方就是连续重复值。比如链表是1 - 2 - 2 - 3要删除2。如果代码里在删了一个2之后把prev也往后移遇到第二个2时就会变成“删掉第一个2留下第二个2”最后结果变成1 - 2 - 3。我见过无数人在这上面卡住甚至一度怀疑选择题库的测试用例有问题。正确的处理方式就是上面哑节点代码里写的只有当前节点不等于val时prev才跟着移动。换句话说prev永远指向“最后一个没有被删除且已经保留的节点”。内存释放也是C/C里绕不开的问题。如果确定要delete被删的节点顺序要格外小心if (cur-val val) { ListNode* tmp cur; prev-next cur-next; cur cur-next; delete tmp; }一定要先把cur-next保存好或者通过prev-next拿到再delete否则删完你连下一个节点都不知道去哪了。3. 反转链表从迭代到递归一次讲透3.1 反转到底反转的是什么反转链表就是把1 - 2 - 3 - 4 - 5变成5 - 4 - 3 - 2 - 1。从结果上看链表的头变成尾尾变成头所有箭头方向反过来。但这里要特别强调链表节点本身物理位置没变变的只是每个节点的next指针指向。想象一下一串项链每个珠子只有一根线连着下一颗。要反转它你必须把每一颗珠子的线头拆下来重新缠到前面那颗珠子上。问题是拆线的时候下一颗珠子的位置你得记在心里否则拆完就找不到了。这正是反转链表核心的“先保存、再修改、后移动”策略。3.2 迭代反转的固定三步迭代法三个指针搞定prev代表当前节点的前一个节点初始化是nullptrcur代表当前要处理的节点next用来保存当前节点的下一个节点。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; // 先保存下一个节点 cur-next prev; // 当前节点指向前一个 prev cur; // prev向后移动 cur next; // cur向后移动 } return prev; }循环里的每一步我建议你对着图走一遍。拿两个节点举例1 - 2。初始prevnullcur1。第一步next2然后cur-nextnull这让1的指针断开成为新链表的尾巴接着prev1cur2。第二轮nextnullcur-next12指向1prev2curnull。循环结束返回2链表变成2 - 1。为什么第一步一定先保存next因为第三步cur-nextprev会把cur原本的next覆盖掉。如果你没有提前保存执行完这行代码后你就再也拿不到原链表的下一个节点了整个链表在后面全是断的。这一步就是防止“断链逃生通道被自己堵死”。3.3 递归反转从后往前推理解newHead怎么传回来递归反转没有迭代那么直观需要一点“假设法”的勇气。递归代码是这样的ListNode* reverseList(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; }它的思想是不要想怎么一次性反转整条链表而是先假设从当前节点的下一个节点开始后面的链表已经反转好了。那head-next就成了反转后链表的最后一个节点而newHead是反转后链表的头。接下来要做的很简单让原来在head后面的那个节点现在是尾部回头指向head再把head的next置空。用1 - 2 - 3推演。reverseList(1)会调用reverseList(2)再调用reverseList(3)。到了3它的next为空直接返回3。回到reverseList(2)newHead是3此时head2head-next是3执行head-next-next head也就是3-next2再让2-nextnull返回3。此时子链表是3 - 2。回到reverseList(1)head1head-next是2执行2-next11-nextnull返回3整条链表变成3 - 2 - 1。递归的本质是“相信子问题已经解决”但很多人在这一步会卡在“为什么head-next-next head不会破坏子链表”。其实不会因为此时head-next还是原链表的下一个节点而它是子链表反转后的最后一个节点最后一个节点的next现在是null正好可以安全地指向head。写过几遍之后你会发现递归反转更像是一个从尾巴倒推回来的过程。3.4 反转的边界、复杂度与常见误区边界情况很简单空链表返回nullptr只有一个节点的链表直接返回它自己。这两种情况在递归的基线条件里天然覆盖了。迭代法时间O(n)空间O(1)递归法时间O(n)空间O(n)调用栈。对绝大多数场景来说迭代法是首选递归法更适合作为思想训练。实际工程中处理超长链表用递归有爆栈风险。常见误区我列一下忘记保存next就修改cur-next链表直接断掉程序输出只剩一两个节点。循环结束后没有把原头节点的next置空反转后的链表尾可能还指向原来的第二个节点造成环形结构或错误输出。返回值搞错。迭代法最后返回prev不是cur因为cur已经变成nullptr了也不是原来的head。如果使用C并在反转过程中释放节点内存别在修改指针前释放不然整个链表就丢了。4. 找链表中间节点快慢指针两步覆盖4.1 常规做法和快慢指针思路对比先想一个最朴素的办法遍历一遍链表数出总长度n然后再从头走n/2步找到的节点就是中间节点。这个思路完全正确但需要两趟遍历。第一趟数数第二趟定位时间依然是O(n)空间O(1)。对于单链表题来说两趟遍历并不是不能接受但面试官一般会追问“能不能一趟搞定”。这时候快慢指针就该登场了。快慢指针的思路特别像两个人同向走路一个人一步走一米另一个人一步走两米。当快的人到达终点时慢的人刚好走了全程的一半站的位置就是中间。ListNode* middleNode(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }一开始slow和fast都指向头节点。每轮循环慢指针走一步快指针走两步。快指针能走的前提是当前节点和下一个节点都不为空。循环退出时slow就是我们要的中间节点。4.2 奇偶数量不同中间点的返回也不同链表节点个数是奇数还是偶数会直接影响中间点的位置这也是这道题最容易出细节问题的地方。奇数个节点比如1 - 2 - 3 - 4 - 5。过程是这样的初始都在1第一轮slow到2、fast到3第二轮slow到3、fast到5第三轮检查条件fast fast-next此时fast指向5但fast-next是null循环退出slow正好停在3。3就是唯一的中间节点没问题。偶数个节点比如1 - 2 - 3 - 4。第一轮slow到2、fast到3第二轮slow到3、fast到null循环退出slow停在3。4个节点的链表中间其实有争议按很多题目默认的“返回两个中间节点中的后一个”3是对的。这里你可能会问如果我想返回两个中间节点中的前一个该怎么办比如1 - 2 - 3 - 4时想返回2。做法也很简单把循环条件改成while (fast-next fast-next-next)。这样快指针在倒数第二步就停慢指针停在偏左的中间位置。这个细节在“回文链表判断”里特别重要因为分割链表的位置偏左还是偏右会直接影响后半段从哪里开始反转。4.3 快慢指针的边界与延伸用途边界处理先记住两条空链表直接返回nullptr只有一个节点时循环条件不满足直接返回head天然正确。快慢指针不止能找中间节点它还有几个经典的延伸检测链表是否有环。让快慢指针从头出发如果链表有环快指针早晚会追上慢指针没环的话快指针会先到达null。找链表倒数第k个节点。可以让快指针先走k步然后快慢指针同步走快指针到终点时慢指针正好在倒数第k个位置。这个思路和找中间节点其实是同一个“距离差”思想的变体。配合反转链表判断回文结构。这是三道题的综合应用后面详细说。提示写while (fast fast-next)时两个条件的顺序不要反过来。如果写成while (fast-next fast)在空链表上会先访问fast-next直接空指针崩溃。条件是“短路的”必须先把fast不为空放在前面。5. 三个题能串出多少种面试变体5.1 变体一删除链表倒数第N个节点这道题是“删除指定值节点”和“快慢指针思想”的结合。思路是先用一个快指针往前走n步然后快慢指针同步往后移动。当快指针到达链表末尾时慢指针的next正好是倒数第n个节点删掉它就行。这里也强烈建议用哑节点。因为如果要删除的节点正好是头节点也就是n等于链表长度时没有哑节点会多一堆特判。用哑节点可以让删除操作统一代码不容易出错。这个变体练完会让你明白一件事删除问题的核心从来都是“找到被删节点的前驱”而不是“找到被删节点本身”。前面删除指定值是通过遍历找前驱这里则是通过快慢指针制造固定距离让慢指针停在正确的前驱位置。5.2 变体二回文链表判断回文链表是快慢指针加反转链表的经典组合题。判断一个链表是不是回文比如1 - 2 - 2 - 1就是回文1 - 2 - 3 - 2 - 1也是回文。常规流程分三步用快慢指针找到链表的中间位置。从中间位置或者中间位置的下一个节点开始反转后半段链表。把原链表前半段和反转后的后半段逐一比较全部相等就是回文。这里面最容易错的就是第二步的起点。偶数长度和奇数长度的分割点不一样反转起点选错比较时就会出现错位。建议初学者在纸上把两种长度的链表各画一个标清slow最终停在哪个节点再决定反转从哪个节点开始。这一步完全依赖前面的基本功所以“找中间节点”这个看似简单的题其实是回文判断的地基。5.3 链表适合这么练的原因与工程启发链表在工程里的应用不如数组那么密集但它的思想无处不在。操作系统的内核链表、内存池里的空闲块管理、浏览器的历史记录栈、LRU缓存淘汰算法里的双向链表都是链表结构。单向链表虽然简单但它是理解指针、引用、动态内存的一把钥匙。算法题为什么这么爱考链表我觉得核心原因是链表题最不依赖数学技巧最依赖逻辑严谨性。没有取模、没有动态规划有的就是一步步改变指针方向、处理边界情况。你写错了它不会像数学题那样“算不出来”而是会编译通过但运行崩溃或者静默地输出一个错得离谱的结果。这种特性让它成为检验代码细节掌控力的经典题型。所以练这三道题不要只满足于“AC了”而是要把每道题的两个解法和每个边界都想明白。到能闭着眼把三种操作串起来分析的程度链表类题目基本就通了。6. 常见问题与调试实录我踩过的坑6.1 容易出现空指针访问的几个位置链表题最常见的运行时错误就是空指针访问。我总结几个高频位置第一个是while (fast fast-next)里的顺序。条件判断是从左到右短路的你要是先写fast-next空链表直接崩溃。同理在循环里访问cur-val之前一定要确认cur不为null。第二个是反转链表里有些人会在循环里顺手写cur cur-next但此时cur-next已经被改成prev了再往后走就把链表彻底走断。正确的做法是用提前保存的next变量来更新cur。第三个是删除节点时prev-next cur-next执行完之后有些人会习惯性地再让prev cur这在普通情况下没问题但在连续删除场景下会漏删前面已经解释过。在代码里如果不确定可以加一行注释标记当前节点的去留。6.2 调试链表题的小技巧很多新手在链表题出错时不会调试只能干瞪眼。我的经验是先写一个辅助打印函数把每个节点的值和地址都打出来void printList(ListNode* head) { ListNode* cur head; while (cur) { std::cout cur-val ; cur cur-next; } std::cout std::endl; }这个函数看起来不起眼但能救很多命。如果打印时发现节点数量不对或者出现环形链表导致死循环你基本就能定位到是指针修改顺序的问题。另外准备一套固定的“标准测试用例”每次调试都跑一遍空链表[]单节点[1]两个节点[1, 2]三个节点[1, 2, 3]含连续重复值的链表[1, 2, 2, 3]全部都是目标值的链表[1, 1, 1]这套用例覆盖了绝大多数边界条件跑一遍出了问题就能立刻看出来是哪一类场景崩了。我发现只用一个例子调通不代表题目真会这些边界用例才是真正检验代码是否健壮的标准。6.3 最后说两句练习心得这三道题我反复写过很多遍每一次都还有新体会。刚开始练的时候我习惯背模板看起来会写但碰到变体就懵。后来改成“先画图再写代码”每道题都在纸上把指针一步步标出来突然就通了。链表算法不是靠记忆是靠对指针流动的直觉。我的建议是把这三个题当成一套组合拳来练。先做删除指定值理解前驱的重要性再做反转链表理解指针重定向的顺序最后做中间节点理解双指针的节奏。练到这步很多链表题的骨架你已经掌握了一大半。以后哪怕忘了某道具体题的写法只要还记得这三板斧就能顺着思路把解法推出来。链表这东西多画图多手写慢慢就不会再怕它了。