刷到了第四天链表专题正式登场。这次的两道题LeetCode 203题“移除链表元素”和707题“设计链表”放在一起刷特别合适一个让你学会“删”一个逼着你把“增删查”整套操作都亲手实现一遍。如果你刚开始刷链表或者链表边界总是写到一半就乱这两题值得当成一个完整的小项目来做。本篇就把我这几小时的心路和踩坑全过程记录下来代码、思路、翻车点全部展开希望对你有点用。1. 先搞懂为什么是这两题链表基本功的“左右手”1.1 链表到底是个啥为什么这么容易让人迷糊链表是由节点串起来的数据结构每个节点里存两样东西当前值val以及指向下一个节点的指针next。最后一个节点的next指向空null。所以链表没有数组那种“连续内存”的物理邻居关系而是一环扣一环的“线索追踪”想找第n个节点只能从头节点开始一个next一个next走过来谁也没法直接跳到中间。这个特性决定了链表题目的核心矛盾一切操作都围绕“怎么不弄丢节点”“怎么正确改变next指向”展开。很多刷题新手对链表恐惧不是不懂原理而是现场写代码时脑子里没有那张“箭头图”。我自己的体会是链表的代码永远跟着图走图漏了代码必错。1.2 203题和707题分别解决什么问题203题是“删除节点”给定一个链表头节点head和一个值val删除链表中所有节点值等于val的节点返回新的头节点。这道题考察的是最基本的删除逻辑以及一个经典陷阱如果被删除的节点是头节点怎么办。网上大量讨论都集中在“虚拟头节点”这个解法上因为不用虚拟头节点就得单独写一套头节点的处理逻辑很容易漏。707题是“设计链表”要求你实现一个MyLinkedList类包含get、addAtHead、addAtTail、addAtIndex、deleteAtIndex五个方法。这道题本身不复杂但它把链表的所有基础操作都打包在一起考察你是否真的理解了“前驱节点”这个概念以及各种index边界该怎么判断。很多人前面单题能过一写完整类就暴露问题就是因为在边界判断和size维护上不够熟练。这两题同步刷的好处在于203题让你把“删除”这个动作练干净707题让你把“插入”和“查找”也补齐。一删一插一查恰恰是链表操作的高频骨架。2. LeetCode 203 移除链表元素虚拟头节点到底妙在哪2.1 先看我最初那个必错的版本很多人一上来会这么写class Solution { public ListNode removeElements(ListNode head, int val) { while (head ! null head.val val) { head head.next; } ListNode cur head; while (cur ! null cur.next ! null) { if (cur.next.val val) { cur.next cur.next.next; } else { cur cur.next; } } return head; } }这段代码能过吗能它是一种“先处理头节点再处理中间节点”的思路。但问题也很明显头节点处理逻辑和普通节点处理逻辑被拆成两段代码不够统一而且很容易遗漏连续两个头节点都要删的情况。虽然上面写了个while来处理但真实考试或者手写代码时很多人只写if于是头节点删完还有一个直接漏掉。我第一反应也是这么写的险险通过。但看评论区公认更稳的做法是虚拟头节点于是第二版我就老老实实用dummy。2.2 虚拟头节点的原理和写法学明白所谓虚拟头节点就是new一个值为任意的节点dummy让dummy.next指向head然后从此只处理“dummy后面跟着谁”最后返回dummy.next作为新head。class Solution: def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]: dummy_head ListNode(0) dummy_head.next head cur dummy_head while cur.next: if cur.next.val val: cur.next cur.next.next # 跳过这个节点 else: cur cur.next # 继续向后走 return dummy_head.next这个解法的核心逻辑是因为虚拟头节点的存在链表里每一个“真实节点”都有前驱。删除动作统一变成“让前驱的next指向前驱的next的next”不需要关心删除的是不是原来的head。这样整个链表被拉到同一条处理线上简洁且不易出错。为什么while条件写cur.next而不是cur因为我们要做的是“判断cur.next需不需要删除”。如果写cur就变成判断当前节点需不需要删除删除当前节点时还得拿着它的上一个节点又绕回去了。所以遍历指针永远停在被删节点的前一个位置这是链表删除题最重要的条件反射。2.3 Java、C版本和关键点对比Java版class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy new ListNode(0); dummy.next head; ListNode cur dummy; while (cur.next ! null) { if (cur.next.val val) { cur.next cur.next.next; } else { cur cur.next; } } return dummy.next; } }C版class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* cur dummy; while (cur-next ! nullptr) { if (cur-next-val val) { cur-next cur-next-next; } else { cur cur-next; } } return dummy-next; } };三个语言思路一模一样。说个容易忽略的点很多同学会担心dummy节点会不会算进链表里最后返回的会不会多个节点。不会因为我们返回的是dummy.next而不是dummy本身。dummy只是一个辅助哨兵在函数结束后就失去引用没有副作用。还需要注意的一个细节是“跳过节点时cur不要移动”。比如链表是1-2-2-3要删2。第一次发现cur.next是第一个2执行cur.next cur.next.next后cur.next变成第二个2此时cur如果后移就会漏掉第二个2。所以跳过分支必须让cur停在原地继续检查新的cur.next。这是最容易踩的坑建议你盯一眼自己的代码看看“删除之后我是不是还在原地”。2.4 复杂度分析和递归思路备个份203题时间复杂度O(n)空间复杂度O(1)只遍历一趟。用迭代已经是最优。如果面试官让你试递归可以这样理解def removeElements(self, head, val): if not head: return None head.next self.removeElements(head.next, val) return head.next if head.val val else head递归的好处是代码非常短符合“只关心当前节点和后继”的思维。缺点是递归深度等于链表长度长链表在工程环境可能爆栈。我建议优先掌握迭代法递归作为思路补充即可因为大多数链表题的工程落地点都是迭代。3. LeetCode 707 设计链表从类和size设计开始3.1 把五个方法的逻辑彻底过一遍707题要求实现这几个方法get(index)获取链表中第index个节点的值。如果索引无效返回-1。addAtHead(val)在链表第一个元素之前插入一个节点。插入后新节点变为链表的第一个节点。addAtTail(val)将节点追加到链表末尾。addAtIndex(index, val)在链表中的第index个节点之前插入一个节点。如果index等于链表长度则追加到末尾如果index大于链表长度则不插入如果index小于等于0则插入头部。deleteAtIndex(index)删除第index个节点索引无效则不操作。这些描述里的“第index个”都是从0开始数的也就是和数组下标一致。很多人在这里会懵但其实你只要统一“从0开始看前驱节点需要走几步”就好。3.2 第一版为什么会写崩我的翻车复盘我第一版写了半小时栽在三个地方。第一忘维护size。get判断无效索引全靠size不维护size循环都不知道走几步还容易出现空指针。第二addAtIndex里插入顺序写反。正确的链表插入顺序是“先把新节点的next指到pre.next再把pre.next指到新节点”。我一开始先改了pre.next导致后半截链表丢失。第三addAtTail我天真地用“找到最后一个节点再插入”但写完发现和addAtIndex(size, val)逻辑完全重复自己还多写了一遍循环。所以第二版我做了调整所有插入操作统一走addAtIndexaddAtHead就是addAtIndex(0, val)addAtTail就是addAtIndex(size, val)。这样设计很干净而且面试时表达出来也显得有模块化意识。3.3 Java版完整实现逐段讲为什么class MyLinkedList { private int size; private ListNode dummy; public MyLinkedList() { size 0; dummy new ListNode(0); } public int get(int index) { if (index 0 || index size) { return -1; } ListNode cur dummy; for (int i 0; i index; i) { cur cur.next; } return cur.val; } public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); } public void addAtIndex(int index, int val) { if (index size) { return; } if (index 0) { index 0; } ListNode pre dummy; for (int i 0; i index; i) { pre pre.next; } ListNode newNode new ListNode(val); newNode.next pre.next; pre.next newNode; size; } public void deleteAtIndex(int index) { if (index 0 || index size) { return; } ListNode pre dummy; for (int i 0; i index; i) { pre pre.next; } pre.next pre.next.next; size--; } }几个关键点重点说。为什么get方法里循环条件是 index因为cur初始在虚拟头节点dummydummy本身不算第0个节点所以要前进index1步才是第index个节点。为什么addAtIndex里循环条件是 index因为我们要找到第index个节点的前驱从dummy到第index个节点的前驱需要走index步。比如index0时循环一次都不走pre就是dummy直接头插indexsize时循环走size步pre会停在原链表最后一个节点上新节点追加到末尾。为什么deleteAtIndex里循环条件和addAtIndex一样同理需要停在待删节点的前驱。找到后pre.next pre.next.next如果删除的是尾节点pre.next.next就是null直接指过去也没问题正好断掉最后一个节点。为什么size要维护get和delete的判断依赖它addAtTail的index也依赖它。每次插入后size删除后size--顺序不能反。如果插入失败index size也就不用改size。3.4 Python版对照适合快速验证思路class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class MyLinkedList: def __init__(self): self.size 0 self.dummy ListNode(0) def get(self, index: int) - int: if index 0 or index self.size: return -1 cur self.dummy for _ in range(index 1): cur cur.next return cur.val def addAtHead(self, val: int) - None: self.addAtIndex(0, val) def addAtTail(self, val: int) - None: self.addAtIndex(self.size, val) def addAtIndex(self, index: int, val: int) - None: if index self.size: return if index 0: index 0 pre self.dummy for _ in range(index): pre pre.next new_node ListNode(val) new_node.next pre.next pre.next new_node self.size 1 def deleteAtIndex(self, index: int) - None: if index 0 or index self.size: return pre self.dummy for _ in range(index): pre pre.next pre.next pre.next.next self.size - 1Python版和Java版几乎一一对应。语言只是外壳链表面试的核心是思路。如果你在本地测试推荐直接用Python版它写起来最快方便验证各种边界。3.5 边界用例测试我现场跑的这一组我写完代码习惯先在纸上跑一遍用例再提交。下面这个组合基本能覆盖所有方法MyLinkedList obj new MyLinkedList(); obj.addAtHead(1); // 链表: 1 obj.addAtTail(3); // 链表: 1 - 3 obj.addAtIndex(1, 2); // 链表: 1 - 2 - 3 obj.get(1); // 返回 2 obj.deleteAtIndex(1); // 链表: 1 - 3 obj.get(1); // 返回 3额外验证空链表场景get(0)size为0应返回-1deleteAtIndex(0)size为0应不操作addAtIndex(3, 5)即时size为2index size应什么都不做addAtIndex(-1, 5)index 0按头插处理还有一个极端场景容易被忽略删除只剩一个节点的链表。比如链表只有一个节点5deleteAtIndex(0)。此时pre是dummypre.next是唯一节点pre.next pre.next.nextpre.next变成nullsize变成0链表清空。没问题。之后再addAtTail(7)其实会变成addAtIndex(0,7)pre从dummy开始走0步插成头节点。逻辑依然正确。3.6 复杂度与优化方向单链表够用双链表更优707题的标准单链表实现addAtHeadO(1)addAtTailO(n)因为需要找到最后一个节点addAtIndexO(index)最坏O(n)deleteAtIndexO(index)最坏O(n)getO(index)最坏O(n)空间复杂度O(n)其实如果想让addAtTail也变成O(1)可以维护一个tail指针但这会让deleteAtIndex尾节点时需要额外判断“删的是不是tail”增加代码复杂度。面试时可以说“我会用单链表实现如果要求尾部O(1)可以改用双链表并维护头尾节点”这样既展示基础能力又体现扩展思维。我实际提交时用的是单链表LeetCode上完全能过。4. 链表题的高频翻车点我整理成了一份速查表4.1 常见问题现象、原因与对策刷这两题的过程中我在讨论区看到最多的问题基本集中在下面表格里。你如果跑代码疯狂报错先对着这个表自查一圈。问题现象根本原因解决思路删完头节点后新头节点没返回直接用了原head头节点改变了但没更新使用虚拟头节点dummy最后返回dummy.next连续重复节点漏删删除节点后cur继续向后移删除分支中保持cur不动继续检查新的cur.nextget返回-1的索引判断反了index size时还应返回-1检查index 0addAtIndex之后链表断了先改了pre.next导致后面的节点丢失先让newNode.next pre.next再pre.next newNode删完节点size忘了减只操作了指针没维护状态在删除分支里同步size--尾部插入后get(size-1)越界size维护错误或者尾插位置写错addAtTail统一走addAtIndex(size, val)while里空指针异常没有判断cur.next为null在访问cur.next.next前先确认cur.next不为null递归解法栈溢出链表太长递归深度太大工程环境选迭代法实现这个表不只在刷题时有参考价值写业务代码时遇到链表操作比如撤销列表、消息队列、LRU链表等同样适用。4.2 调试链表的三个实战技巧第一个技巧是本地准备一个打印链表的小工具。刷题平台有时候不好打印中间过程你在本地写一个方法def print_list(head): vals [] cur head while cur: vals.append(str(cur.val)) cur cur.next print( - .join(vals) - null)在关键步骤前后打印一次链表指针乱不乱立刻清楚。第二个技巧是“画图”。链表题千万别在脑子里硬推。三步画图法就够了先画出初始链表箭头再标出pre和cur的位置最后画出执行一行代码后箭头怎么变。707题的addAtIndex插入逻辑我画了三次才彻底确认插入顺序。第三个技巧是“边界三连问”。每次写完代码都主动问自己三个问题空链表能跑吗只有一个节点能跑吗删除最后一个节点能跑吗用这三个问题能揪出八成空指针问题。4.3 刷链表题的一个通用套路五步法这两题刷完我总结出自己处理链表题的固定动作题目里提到“删除节点”先在纸上决定要不要虚拟头节点。只要头节点可能变化就上dummy。给指针起名。统一用pre表示前驱cur表示当前节点防止写着写着两个指针混了。找出“被操作节点的前驱是谁”。删除和插入都只需要拿到前驱这是链表操作的关键。在动手改next之前检查是否需要先保存某个节点。插入节点时先接新节点再断旧链顺序永远别反。最后检查size和返回头。707题别忘了size203题别忘了返回dummy.next而不是dummy。这套五步法不一定玄妙但确实减少了很多无头绪的debug时间也让我再遇到链表题时心理压力小了很多。5. Day4之后的一些私人体会5.1 链表的本质是“状态一致”和“边界意识”刷完203和707最大的感受不是学了两道题而是把链表的几个核心习惯固定下来了。链表题目听起来很多翻转链表、删除中间节点、合并两个链表、找环、相交链表翻来覆去都是同一件事在正确的时间把正确的next指向正确的地方。而保证这个“正确”的就是虚拟头节点和边界检查。以前我也觉得链表题靠“想象力”后来发现靠的是流程。每天写链表题之前先默念dummy要不要、pre是谁、size改不改能挡住大多数低级错误。5.2 一个可以继续扩展的小方向707题我做的是单链表但LeetCode评论区很多人还会用双链表做。双链表的好处是addAtTail可以直接用tail.prev处理不需要从头遍历坏处是每个方法里多维护两个方向的指针代码量明显上去。如果你想挑战自己可以把707改成双链表版本看看同样的五个方法边界判断哪里变了哪里没变。这个练习对你后面刷LRU缓存这类高频题会非常有用。很多LeetCode热门100题后续会频繁用到链表和其他数据结构的组合比如合并K个升序链表、反转链表II、环形链表等它们的基本功都来自今天这两题。把203和707吃透等于给后面的路修好了地基。5.3 关于做题节奏的一个想法Day4一口气刷两题没有贪多我觉得这个节奏是对的。链表题靠的不是数量而是每一题的边界有没有被真正理解。我宁可花两小时把707的每个边界情况都写成测试用例也不愿意十分钟默写完代码然后转头就忘。刷题这个事慢就是快你把最基础的链表“增删查”亲手实现一遍后续很多“高级技巧”都能自然接上。