★ FEATURED ARTICLE 1. 训练营第三天为什么偏偏是这四道链表题代码随想录算法训练营第三天任务是四道链表相关的题目203.移除链表元素、707.设计链表、206.反转链表、92.反转链表II。如果只看数量四道题不算多但真正做下来会发现这四道题是按一条隐藏逻辑线排好的先解决“链表操作的基础防线”再让你自己手写一个链表来彻底理解结构然后用反转把这个结构的特性吃透最后用一道“部分反转”把你前面的理解拧成一股绳。我在刷题群里看到不少同学第一天兴冲冲第二天开始皱眉到了第三天直接心态崩了。原因很简单链表的题目不像数组题那样有天然的“下标”直觉很多操作需要自己在脑子里模拟指针的移动。如果之前没有系统接触过链表直接上手203和206确实容易卡住。但反过来说链表恰恰是算法面试里的高频考点而且一旦掌握了套路它是所有数据结构里最“有手就行”的一类题——比动态规划友好太多了。这篇文章我不打算复述题解而是想以训练营第三天的实际学习记录为切入点把四道题背后的共同解题逻辑、我踩过的坑、以及一些题解里不会明说的判断依据讲清楚。无论你是正在跟训练营的学员还是自己刷LeetCode的独立学习者只要把这一篇里的思路理顺后面遇到链表相关的题目心里会稳很多。2. 虚拟头结点的妙用203.移除链表元素的真正难点2.1 为什么要引入虚拟头结点移除链表元素这题乍一看非常简单遍历链表遇到val等于目标值的节点就让前一个节点的next直接指向当前节点的next。这个逻辑数组里也类似但链表有个特殊之处——如果你要删除的是头结点你没有“前一个节点”。这是很多初学者第一次被链表“毒打”的地方。处理方式通常有两种一种是单独判断头结点是否要删除如果要删就移动头指针另一种是引入一个虚拟头结点dummy head让原来的头结点也变成一个“普通节点”这样就统一了删除逻辑。我当时用的是虚拟头结点方案因为训练营的题解也是这么写的。虚拟头结点的本质是你手动创建一个值为任意常用0或-1的节点它的next指向原链表的头结点。这样一来整个链表的所有节点都拥有了前驱节点删除逻辑只需要一种写法不需要特判头部。这是一种典型的“哨兵位”思想后面的很多链表题都会用到。2.2 双指针遍历的写法细节具体实现上我建议用cur和prev两个指针prev指向当前节点的前一个节点cur指向当前节点。从头开始遍历如果cur.val等于目标值就让prev.next跳过cur否则prev移动到cur的位置。无论是否删除cur都要移动到下一个节点。这里有个容易出错的小细节删除节点后prev不需要移动。因为删除后prev.next已经指向了cur的下一个节点此时prev依然是“新当前节点”的前驱。如果这里多移动一步就会跳过下一个节点导致漏判。我在第一次写的时候就在这里栽了跟头——把删除分支里的prev也往后挪了结果测试用例里连续出现两个相同值的时候第二个值没被删掉。另外哨兵节点的内存释放问题。在C里dummy节点是new出来的遍历完记得delete否则会内存泄漏。训练营里用C的同学不少这个点经常被忽略但不影响功能所以很多题解干脆不提。我的建议是刷题阶段用不用智能指针都行但心里要清楚这个节点是自己创建的写C的时候别忘了清理写Java和Python的同学就没有这个烦恼垃圾回收机制会处理。2.3 为什么虚拟头结点比“单独处理头结点”更好单独处理头结点其实也能AC代码也不复杂。但有一个问题如果链表从头结点开始连续多个节点都要删除单独处理头结点的写法需要写一个循环直到头结点不是目标值或者链表为空。这个循环很容易写错边界。相比之下虚拟头结点把“头部删空”的情况变成了“中间删节点”的普通场景逻辑上更统一也不容易漏。更重要的是这种“加一个哨兵”的思路在707.设计链表里同样适用。训练营把203安排在第一天很可能就是为707做铺垫的。如果203你只是背了代码没有理解虚拟头结点的意义那做707的时候大概率还要再卡一次。3. 707.设计链表把结构彻底吃透的一道题3.1 五种操作的边界条件设计链表要求实现五个功能get(index)、addAtHead(val)、addAtTail(val)、addAtIndex(index, val)、deleteAtIndex(index)。这道题本质上不是为了让你写出多漂亮的算法而是逼迫你亲手实现一个链表的所有基本操作。只有自己实现过一遍你才会真正理解为什么很多链表题在调试时那么容易越界。我用的定义是链表节点包含val和next链表类维护size和dummyHead。维护size这个变量非常关键很多操作尤其是get和addAtIndex都需要先判断index是否合法有一个size变量可以直接判断不用每次遍历统计。边界条件的判断是这道题的核心。我总结了一下get(index)index 0 或 index size直接返回 -1。addAtIndex(index, val)index size 则不加index 0 时插入头部index size 时插入尾部其他情况找到前驱节点插入。deleteAtIndex(index)index 0 或 index size直接返回。这里有同学会问为什么addAtIndex里index size就是尾部插入因为链表的索引从0开始当size等于3时有效索引是0、1、2而节点3正好是尾节点之后的“空位”。所以index size恰好表示追加到末尾。3.2 遍历逻辑的统一写法实现的核心是“找到第index个节点的前驱节点”。不管是插入还是删除都要先找到前驱。怎么找从dummyHead出发移动index步就能到达第index个节点的前驱。我举个例子如果链表是 1 - 2 - 3size是3dummyHead指向1。要删除索引为1的节点值为2需要找到索引为1节点的前驱即索引为0的节点。此时从dummyHead开始移动1步到达索引0的节点值为1然后让它的next指向值为2节点的next即值为3的节点。整个过程非常机械但你需要特别小心“移动几步”。这里我要强调一个经验写链表题的时候永远画图。不要嫌麻烦你脑子里想象的指针移动和实际发生的往往不一样尤其是涉及到连续插入、删除的时候。训练营的A同学之前写addAtIndex时总觉得自己已经找到了正确的位置但测试就是报错。后来他在纸上画了两条链一条是插入前一条是插入后标出prev和newNode的位置一下就看出问题所在。3.3 我踩过的一个隐蔽坑我踩过的一个坑是在addAtTail时直接用了一个cur指针从头遍历到尾然后让cur.next newNode。这本身没问题但问题是我忘记更新size了。get的时候一直返回-1排查了半天才意识到是size没有自增。这种错误很蠢但在训练营的高强度刷题节奏下非常容易犯因为addAtTail的代码看起来太简单了容易让人忽略维护size。另外一个坑是deleteAtIndex时如果删除的是最后一个节点pre.next pre.next.next之后忽略了检查pre.next是否为null。虽然Java里不会报错但如果你在delete后还试图访问删除节点的值比如某个教程里打印被删除节点的值就会得到null。刷题阶段建议只要删除完就立刻把pre.next指向合适的值不要再持有旧引用。4. 反转链表的两种路径206.反转链表的递归与迭代4.1 迭代法就地反转的核心逻辑反转链表是链表题里最经典的题目也是训练营第三天里含金量最高的一道。解法通常有两种迭代和递归。迭代法的核心思路是遍历链表把每个节点的next指针指向前一个节点。听起来简单但第一次写的人很容易被绕进去。我的迭代写法是维护三个指针prev前驱初始为null、cur当前节点初始为head、nextTemp保存cur的下一个节点。每一步处理用nextTemp保存cur.next因为马上要修改cur.next了不保存就丢失了。将cur.next指向prev。将prev移动到cur。将cur移动到nextTemp。这里最关键的是第一步和第二步。很多初学者写的时候会忘记保存下一步的节点或者在修改cur.next之后才发现后面的链表已经丢了。你可以在纸上模拟一下比如1 - 2 - 3 - nullpre是null。第一步后pre还是nullcur是1nextTemp是2第二步后1的next变成null此时1和后面断开了如果没有nextTemp后面的2和3就永远找不到了。迭代法的循环条件是cur ! null最后返回prev。这个条件非常关键退出循环时cur已经是null而prev指向最后一个非空节点也就是反转后的新头。4.2 递归法从后往前的思维切换递归法相对难理解但代码极短。核心思路是先反转头结点之后的所有节点然后让原本头结点的next节点即反转过后的尾节点也就是原链表的倒数第二个节点的next指向它自己。我之前看到递归解法时总觉得像魔法后来想通了一个比喻递归就像你让一个队伍从队尾开始向后转每个人都转身然后让你的下一个队友转过身来之后你再把手指向他身后的方向。关键在于“信任”——你相信递归调用的返回值就是“反转后的新头”你只需要处理当前节点和它的下一个节点之间的关系。具体代码逻辑是如果head为null或者head.next为null直接返回head。调用reverse(head.next)拿到反转后的新头newHead。此时head.next指向原链表的第二个节点而这个节点在反转后变成了倒数第一个节点它的next正好是null。让head.next.next head把原第二个节点指向原头结点。让head.next null断掉旧的指向。返回newHead。这里最难理解的是第2步你会觉得“我还没有反转完啊怎么就递归了”但递归就是这样它假设子问题已经解决。你只需要把所有状态更新放在递归调用之后即可。4.3 迭代vs递归训练营里该怎么选我个人的建议是单纯为了通过这道题迭代法更容易写对尤其在线面试手写代码的场景下迭代法更不容易出错。但递归法值得理解因为92题反转链表II用递归法会简单很多而且很多大厂面试官会追问递归思路。另外递归有一个潜在的系统栈风险。如果链表的长度非常大比如几万个节点递归可能栈溢出。迭代法就不存在这个问题。所以如果是项目里真需要反转一个很长的链表我优先用迭代。刷题阶段两者都可以过建议先写迭代再死磕递归。5. 部分反转的进阶92.反转链表II的思路拆解5.1 先定位边界再局部反转92题要求在区间 [left, right] 内反转链表。如果你已经熟练掌握了206的迭代反转这道题的关键就不是“怎么反转”而是“如何在反转后把链表拼接回去”。我的思路分三步找到left位置的前驱节点用prevLeft记录。从left位置开始反转right-left1个节点。让prevLeft的next指向反转后的新头让反转后的新尾的next指向原本right位置的下一个节点。这个思路和训练营题解一致但真正写的时候有个容易忽略的点head可能发生变化。如果left等于1那么反转后的新头就是整个链表的头。所以不能直接返回head而要先判断是否修改了头部或者干脆用dummyHead统一边界。5.2 dummyHead在此题中为什么是“必需品”在92题里如果left等于1prevLeft就是dummyHead这样一来不管left是不是1处理逻辑都统一了不需要看head是否改变直接返回dummy.next即可。我在206里不用dummyHead也能写清楚但在92里如果不加dummyHeadleft为1时会非常别扭——要么单独判断要么用一个额外的标志变量记录新头。这里也印证了一个规律链表题里只要有“可能修改头结点”的情况dummyHead几乎都是最优解。203是707是92也是。一旦你习惯了这个套路刷题效率会大幅提升。5.3 部分反转的代码模板很多题解会给出一个标准的局部反转模板先用一个for循环把prevLeft移动到正确位置然后用三个指针反转区间内的节点最后连接。我建议直接把下面这个模板背下来它兼容206和92public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 0; i left - 1; i) { pre pre.next; } ListNode cur pre.next; ListNode next null; for (int i 0; i right - left; i) { next cur.next; cur.next next.next; next.next pre.next; pre.next next; } return dummy.next; }这个模板的巧妙之处在于每次循环把next节点“摘下来”头插到pre后面。整个过程不需要像206那样维护prev指针因为pre始终指向反转区间的前驱。第一眼看到这个代码可能会觉得有些绕我建议你在纸上按题目给的例子走一遍比如 1 - 2 - 3 - 4 - 5left2right4。走完后你会发现区间内的节点就像剥洋葱一样从第一个开始挨个被提到了pre后面。5.4 为什么很多题解都强调“一趟遍历”92题的常规解法是找到边界后反转理论上需要两趟一趟定位left一趟反转。上面给的头插法其实也只用了两趟但代码长度更短。面试时面试官可能会问“能否只遍历一趟”其实用递归法可以做到。但我不建议在训练营第三天就追求这个先把基础写稳再考虑优化这是训练营的整体节奏。6. 时间复杂度的横向对比这四个题的实际运行效率很多人刷链表题的时候不怎么关心复杂度因为链表不像数组那样有大规模数据压力。但训练营要求每题都分析复杂度。我把四道题的复杂度列在下面方便你对照题目时间复杂度空间复杂度关键操作203.移除链表元素O(n)O(1)遍历删除707.设计链表O(n)O(1)按索引查找最坏O(n)206.反转链表迭代O(n)O(1)三指针原地反转206.反转链表递归O(n)O(n)系统栈空间92.反转链表IIO(n)O(1)定位边界局部反转707设计链表这里要特别说明get、addAtHead、addAtTail、addAtIndex、deleteAtIndex除了addAtHead和addAtTail在维护dummyHead和tail的特殊技巧下可以做到O(1)其他操作因为要遍历查找所以最坏O(n)。训练营里很多同学以为addAtHead必然是O(1)但如果你是用dummyHead实现addAtHead确实就是O(1)因为dummyHead.next就是头结点直接插入即可。关于递归的空间复杂度我见过不少博文写的是O(1)这是不对的。递归调用会占用系统栈每个递归层级都会压栈所以最坏空间是O(n)。刷题时如果你对空间的敏感度不高可能无所谓但面试时被问到这个点答错会很减分。7. 训练营学习中的高频报错与排查策略7.1 节点被“自引用”导致的死循环这是我写206的时候遇到的最诡异的问题反转后的链表的最后一个节点它的next指向自己。具体表现是运行测试用例时无限循环或者打印链表时出现节点重复。原因通常是递归反转的代码中忘记将原头结点的next设为null。比如如果原链表只有一个节点反转前head.next本来就是null没问题。但如果链表有两个节点递归后原头结点的next应该设为null否则它还会指向原第二个节点而原第二个节点已经反转并指向原头结点这样两个节点就形成了环。如何快速排查我建议在反转后加一个调试打印遍历链表20次看是否越界。如果会无限重复那就百分百是环。手动检查纸上的指针图比阅读代码更容易发现这个问题。7.2 用“纸笔模拟”替代“脑内模拟”训练营第一周最常见的问题是代码写完了但不知道哪里错了。链表題和数组题不一样数组用IDE调试时可以看到index的移动链表在调试器里的可视化效果很差。所以我的习惯是遇到边界条件比较多或容易出环的题一定在纸上画两个状态——操作前的链表、操作后的链表。以92题为例你可以在纸上画出left-1位置的节点pre以及反转区间内每个节点的前后关系。标出pre.next和cur在每一轮循环后的位置。不要嫌慢训练营第三天画三四个图每个图都画对比盲目提交30次效率高得多。7.3 把“越界”错误当成“边界条件没写全”的信号很多链表题报错是null pointer exception比如访问cur.next时cur为null。这种报错在训练营群里几乎每天都能看到。实际上它对应的往往是代码里缺少对边界条件的判断。比如707的get中index 0或index size时直接返回-1如果漏了index 0的判断在index为负的情况下你会访问到dummyHead之前的节点自然报错。我的排查策略是找到报错的那一行向上回看三行代码看看有没有一个if判断漏了边界。比如如果报错点在addAtIndex中检查是不是漏写了index size的判断如果在deleteAtIndex检查是不是没判断index 0。链表题经常是“先判断后操作”顺序错了问题就来了。8. 训练营第三天之后的复盘建议8.1 四道题的“共同套路清单”我建议你在第三天结束时自己写一份“链表操作套路清单”包括以下几点需要删除节点时优先考虑虚拟头结点避免单独处理“头结点即目标”的情况。手写链表设计题时一定维护一个size变量所有操作都先基于size判断合法性。反转区间链表时先找前驱再局部反转最后拼接dummyHead统一头部变化。递归反转时处理好base casehead为null或head.next为null记得把原头结点的next置空。写每个操作前先明确需要维护的指针数量最好在纸上画出来再动手。这些结论不是训练营给的而是我自己做第三天的题复盘时总结出来的。如果你只把四道题的代码记下来不去总结那第三天就白过了。8.2 一道题做三遍训练营的隐藏学习法我自己的学习节奏很固定第一遍看题限时30分钟独立写第二遍看完官方题解理解思路合上答案重新写一遍第三遍隔一天再写一次检验是否真的掌握了。训练营节奏快很多人只做一遍就赶进度但链表这种基础结构不做三遍根本不牢固。92题尤其适合三遍法第一遍你可能根本写不出来第二遍照着模板写第三遍你会发现不需要看题解也能在10分钟内写出正确的代码。这个过程能建立起你用迭代法反转局部链表的“肌肉记忆”。8.3 我练完这四道题后的一个明显变化说实话第四天开始做新题的时候我发现自己对链表的恐惧感小了很多。以前看到“反转链表II”这种题脑子里会觉得“头要变、尾要变、中间还要反转太复杂了”。但练完这四道之后我看到类似的题会先问自己几个问题头结点会不会变有没有interval有没有删除然后直接选用模板。我建议你也可以在训练营群里找一个刷题搭子互相讲题。不要小看讲题这个过程我发现自己能把别人讲懂的时候才是真正理解的时候。训练营第三天不仅是四道题更像是链表基本功的集中突破——跨过这个坎后面二叉树、回溯、动态规划再难你至少不会因为基础薄弱而卡壳。
阅读完成 · 觉得有帮助？
