最近在给团队做算法内训的时候我发现一个挺有意思的现象不少候选人刷题量并不少动辄三四百题但碰到“螺旋矩阵、移除链表元素、设计链表”这三道题时反而比那些只认真啃过几十道题的人更容易翻车。原因也不复杂——这三道题都不涉及什么高深算法思想考的全是基本功二维数组的下标边界、链表节点的指针操作、类结构的设计取舍。恰恰是这种“看起来简单”的东西最考验一个人写代码的严谨程度和底层理解。这篇文章我把这三道题放在一起拆一遍讲讲它们背后的共同主线、每道题的关键实现细节以及我在实际面试和 code review 里反复见到的错误。无论你是准备笔试的在校生还是想补基础的后端开发这组题都值得花一个下午认真过一遍因为它们在面试里真的出现得太高频了。1. 三道题放一起练练的是同一套基本功先说个很多人没意识到的事这三道题表面上分属“数组类”和“链表类”但它们考核的能力高度重合。螺旋矩阵考的是二维数组遍历时的边界管理——什么时候向右、什么时候向下、什么时候收缩边界本质上是对一层一层“圈”的状态维护。移除链表元素考的是单链表遍历时的指针维护——前驱节点怎么跟、当前节点怎么移动、删除后链怎么接。设计链表则更进一步考的是把链表的结构特性和操作语义完整实现出来——增删查的位置约定、索引的合法性判断、头尾操作的特殊处理。把它们连起来看其实就是一套东西你面对一个线性/类线性的数据结构时能不能把“位置”“边界”“状态”这三件事管明白。我见过太多人刷题只记住“这题用双指针”“那题用栈”但遇到这三道题就卡住。因为他们背的是题型结论不是数据结构本身。螺旋矩阵背了“左到右、上到下、右到左、下到上”结果碰到 1 行 5 列的矩阵输出直接多出来一堆重复元素移除链表元素背了“dummy 节点”却说不出 dummy 到底解决了什么设计链表背了模板却不知道为什么有的写法要在 addAtIndex 里单独判断 index size。所以我强烈建议这三道题不要当普通题刷要当作自检题。如果你能在不看题解的情况下把这三道题都写对、写顺能讲清楚每一步为什么这么写那数组和链表的基本功基本就过关了。如果写不利索那后面的高级题大概率也是空中楼阁。2. 螺旋矩阵边界收缩法的完整推导与“越界”深渊2.1 先确定策略为什么不用方向数组螺旋矩阵LeetCode 54的输入是一个 m×n 矩阵要求按顺时针螺旋序返回所有元素。大多数人第一次做这题会想到方向数组加 visited 标记定义 right、down、left、up 四个方向遇到边界或已访问就转向。这个方案能跑通但我基本不用。原因有两个它需要额外 O(m×n) 的 visited 空间面试官经常追问“能不能 O(1) 额外空间”方向数组方案的代码里要维护“当前位置 当前方向 下一步合法性判断”三套状态容易写得绕也容易在转向时出错。边界收缩法shrink boundaries是更优雅的方案用 top、bottom、left、right 四个变量维护当前未遍历的矩形区域每遍历完一边就收缩对应边界。循环条件用left right and top bottom。2.2 代码实现与每一步的含义class Solution: def spiralOrder(self, matrix: List[List[int]]) - List[int]: if not matrix or not matrix[0]: return [] top, bottom 0, len(matrix) - 1 left, right 0, len(matrix[0]) - 1 res [] while left right and top bottom: # 1. 从左到右遍历当前上边界整行 for j in range(left, right 1): res.append(matrix[top][j]) top 1 # 上边界下移 # 2. 从上到下遍历当前右边界整列 for i in range(top, bottom 1): res.append(matrix[i][right]) right - 1 # 右边界左移 # 3. 从右到左遍历当前下边界整行 # 注意必须先判断 top bottom防止单行矩阵重复 if top bottom: for j in range(right, left - 1, -1): res.append(matrix[bottom][j]) bottom - 1 # 下边界上移 # 4. 从下到上遍历当前左边界整列 # 注意必须先判断 left right防止单列矩阵重复 if left right: for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) left 1 # 左边界右移 return res第 3、4 步里面的两个if判断是整个算法的灵魂。没有它们当矩阵只剩一行或只剩一列时会走出重复元素。2.3 单行单列矩阵是坑王拿一个 1×5 的矩阵[[1, 2, 3, 4, 5]]来走一遍初始top0bottom0left0right4。第 1 步遍历整行输出 1、2、3、4、5然后 top 变成 1。此时top bottom但 while 条件还没检查进入第 2 步。不过第 2 步的循环for i in range(top, bottom 1)即range(1, 1)不执行right 照常减 1 变成 3。接下来如果没有if top bottom的保护第 3 步会从 right3 往左遍历到 left0把 4、3、2、1 再输出一遍——这就重复了。单列矩阵同理是因为第 4 步缺少if left right的保护。我见过最可惜的错误就是原理讲得头头是道代码里忘了这两行判断测试用例一跑 3×3 全对一跑 1×1 或 3×1 就直接崩。所以写完这段代码第一件事就是测这几种边界形状空矩阵、1 行、1 列、1×1 矩阵。这比跑 10 个常规用例都有用。2.4 复杂度与手推练习建议时间上每个元素访问一次O(m×n)空间上除了输出数组只用了四个边界变量O(1)。这也就是为什么这个解法在面试里几乎是标准答案。给一个实操建议写代码之前先拿笔在一个 3×4 的矩阵上把四步遍历手推一遍标出每一步之后 top/bottom/left/right 分别变成什么。你只要完整推过两遍就会发现边界收缩法的逻辑是每走完一步就自闭一条边——它不是一个“走格子”的思路而是一个“剥洋葱”的思路。理解了这一点后面做螺旋矩阵 II按螺旋顺序填充矩阵就是同构的甚至更简单。3. 移除链表元素虚拟头节点这个设计到底妙在哪3.1 不用 dummy 的话麻烦在哪移除链表元素LeetCode 203要求删除链表中所有值等于 val 的节点返回新头节点。最朴素的做法是维护一个 prev 指针找到目标节点后让prev.next cur.next。但这里有一个绕不开的痛点如果头节点本身就要被删除情况会变得很尴尬。你可以单独写一个while head and head.val val: head head.next的循环先处理头节点但这样每次写链表删除都要重复这种特判代码也不够统一。还有更隐蔽的问题如果把删除逻辑写成 “点击当前节点判断是否要删”那在删掉 cur 之后prev 要不要移动如果你写成prev cur而 cur 又被删了就相当于前驱指针跑到一个已删除节点上后续操作很容易踩空。3.2 dummy 节点统一了所有情况虚拟头节点的做法是这样class Solution: def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]: dummy ListNode(0, head) # 虚拟头next 指向真实头 prev dummy cur head while cur: if cur.val val: # 删除当前节点前驱直接跳过它 prev.next cur.next else: # 没被删除前驱才往前走 prev cur cur cur.next return dummy.next这段代码的两个关键设计dummy 节点让所有删除逻辑完全统一。即使原链表第一个节点就是要删的处理方式也和其他节点完全一样——prev.next cur.next。你不需要担心“删头节点会不会丢链表”。prev 只在当前节点不需要删除时才移动。当 cur 被跳过时prev 保持不动继续指向新链表里 cur 的前驱当 cur 保留时prev 移到 cur 的位置。这个“动还是不动”的决策在链表删除类问题里会反复出现几乎是个万能套路。3.3 递归写法也值得理解链表问题很多人只用迭代但其实递归版本对理解“解法”很有帮助class Solution: def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]: if head is None: return None head.next self.removeElements(head.next, val) return head.next if head.val val else head递归的核心视角是把删除操作定义在“当前节点 结果链表”的转换上。先递归处理后面的链表然后看当前节点——如果当前节点的值等于 val整个当前节点就不要了直接返回已经处理好的子链表否则把当前节点接在子链表前面。递归的空间复杂度是 O(n)因为调用栈深度和链表长度成正比对超长链表有栈溢出风险。但它的思维模式和迭代完全不同建议两种写法都掌握。面试时优先写迭代被问到“还有没有别的方法”再补递归。3.4 如果用的是 C/C记得处理释放问题看到很多 C 候选人只写了prev-next cur-next忘了delete cur。在 LeetCode 上不释放也能过因为 OJ 不检测内存泄漏但真实工程里这就是活生生的内存泄漏。C 正确写法是ListNode* toDelete cur; prev-next cur-next; cur cur-next; delete toDelete;注意顺序先保存待删除节点指针再更新链最后释放内存。如果先cur cur-next再delete cur等于把链也一起删了。这种细节面试官特别喜欢追问毕竟链表题的核心考点之一就是“指针操作的正确顺序”。4. 设计链表用双向链表配合哨兵节点写出零边界烦恼的类4.1 题目要求和关键决策点设计链表LeetCode 707要求自己设计一个链表类实现 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法。这道题和前面两题不一样它不是让你用现成的链表解题而是让你从零实现一个可用的链表结构。动手之前有两个关键决策第一个决策用单链表还是双向链表单链表实现 addAtHead 和 addAtTail 都不难但 deleteAtIndex 遇到“删除最后一个节点”时需要从头遍历到倒数第二个节点麻烦一点。双向链表每个节点都持有 prev 和 next删除任意节点只需要 O(1) 找到前驱后继。代价只是每个节点多一个指针。既然是自己设计我建议直接上双向链表逻辑更顺面试追问起来也更有底气。第二个决策用不用哨兵节点sentinel node这是整个设计的分水岭。如果不加哨兵空链表的头尾操作全是特判addAtHead 时要判断 head 是否为 nulladdAtTail 时要维护 tail 还要处理“链表是空”的情况delete 时更是头尾两头开花。代码会被 if 埋没。加两个哨兵就舒服了一个虚拟头节点 head一个虚拟尾节点 tail真正的数据节点都夹在两者之间。核心思想是不管链表有没有数据head 和 tail 永远存在所有的操作都在 head 和 tail 之间进行边界情况被自动吸收掉了。4.2 完整实现以 index 定位法串联所有方法class ListNode: def __init__(self, val0, prevNone, nextNone): self.val val self.prev prev self.next next class MyLinkedList: def __init__(self): self.head ListNode() # 虚拟头 self.tail ListNode() # 虚拟尾 self.head.next self.tail self.tail.prev self.head self.size 0 # 实际节点个数 def get(self, index: int) - int: if index 0 or index self.size: return -1 cur self.head.next for _ in range(index): cur cur.next return cur.val def addAtHead(self, val: int) - None: node ListNode(val) nxt self.head.next self.head.next node node.prev self.head node.next nxt nxt.prev node self.size 1 def addAtTail(self, val: int) - None: node ListNode(val) prv self.tail.prev prv.next node node.prev prv node.next self.tail self.tail.prev node self.size 1 def addAtIndex(self, index: int, val: int) - None: if index 0 or index self.size: return if index 0: self.addAtHead(val) return if index self.size: self.addAtTail(val) return # 找到当前 index 位置的节点新节点插到它前面 cur self.head.next for _ in range(index): cur cur.next prv cur.prev node ListNode(val) prv.next node node.prev prv node.next cur cur.prev node self.size 1 def deleteAtIndex(self, index: int) - None: if index 0 or index self.size: return cur self.head.next for _ in range(index): cur cur.next prv cur.prev nxt cur.next prv.next nxt nxt.prev prv self.size - 14.3 几个你必须理解的细节维护 size 是偷懒吗不是是智慧。有了 sizeaddAtIndex 和 deleteAtIndex 的合法性判断是 O(1) 的。如果你不做 size 统计就得靠遍历去数节点判断越界那 get 本来就 O(n)再叠加一层遍历复杂度就更难看了。很多新手在实现链表类时不维护 size写到最后自己都被绕晕。addAtIndex 的边界区间是 [0, size]。这个别记错了。index 等于 size 时等价于尾插index 等于 0 时等价于头插index 小于 0 或者是大于 size按题目要求直接不操作。注意是“大于 size”而非“大于等于 size”因为 size 位置是合法的尾插位置。双向链表的插入/删除四步别乱序。插入一个新节点本质是把“前驱的下一个”和“后继的前一个”这两条线掰向新节点。我习惯固定顺序先处理新节点的 prev 和 next再处理原前驱的 next最后处理原后继的 prev。删除的时候正好相反先摘除节点再让前驱的 next 指向后继、后继的 prev 指向前驱。顺序不乱就没有“节点引用悬空”的烦恼。4.4 工程视角为什么真实项目里也用这种结构真实项目里这种“链表 哨兵 size 记录”的设计一点也不罕见。最典型的就是LRU Cache 的经典实现——用 HashMap 存 key 到节点的映射用双向链表维护访问顺序哨兵节点保证链表头和尾的操作统一。我面试过不少候选人能把 LeetCode 三题背得很熟但问“LRU 里为什么用双向链表而不是单向”就说不清楚。答案恰恰就藏在这一题的设计决策里删除任意节点时双向链表可以 O(1) 拿到前驱而单链表必须从头遍历找前驱。所以你先懂了设计链表这题中的“为什么双向”LRU 这类进阶题就是一层窗户纸。5. 面试追问方向三道题背后能延伸出多少变种刷完三题拿到“正确 AC”只是第一步。面试官关心的是你能不能举一反三。我总结几个高频的追问方向每个方向都能在刷题平台上单独成题。5.1 螺旋矩阵的变体螺旋矩阵 IILeetCode 59给定 n按螺旋顺序填一个 n×n 矩阵。核心逻辑和螺旋矩阵 I 完全同构只是把“读元素”换成“写元素”边界收缩的顺序不变。建议这道题和螺旋矩阵 I 一起刷两个方向都跑通你对边界收缩的理解才真正到位。对角线遍历LeetCode 498虽然是另一种遍历方式但考的依然是“将矩阵按特定顺序组织成线性序列”的能力。面试官常常把这题作为螺旋矩阵的“平行替换”看看你是不是只会背套路。旋转图像LeetCode 48原地旋转矩阵核心是四角交换的分区处理。它是矩阵下标运算的进阶考验比螺旋矩阵更抽象但基本功还是“下标映射”。5.2 链表删除和操作的变体删除链表的倒数第 N 个节点LeetCode 19双指针利器fast 先走 N 步然后 slow 和 fast 同步走。这里面也有删除链表的“前驱维护”问题而且因为要删倒数第 N 个通常也建议用 dummy 节点统一处理头节点删除。两两交换链表中的节点LeetCode 24迭代版需要维护三个指针递归版思路更清晰但指针之间的先后顺序极其容易搞错。它考的东西和移除链表元素本质一样在链表中正确完成“重接”操作。链表相交LeetCode 160和环形链表 IILeetCode 142这类题考察双指针在链表结构上的移动规律。它们没有删除操作但如果你对链表指针的移动不敏感解题时就会很吃力。5.3 设计类题目的延伸LRU 缓存LeetCode 146这是设计链表最经典的延伸。HashMap 负责 O(1) 查找双向链表负责 O(1) 增删和顺序调整。你会发现设计链表这题里的哨兵节点、size 维护、指针四步操作在这里一个都不少只是加了一层映射关系。设计跳表LeetCode 1206如果你能设计完链表后立刻设计跳表面试官基本会认为你的数据结构功底是扎实的。跳表本质上是“多层级链表”每个节点有多个前进指针插入时按概率决定层数。做这题之前链表的基础操作必须形成肌肉记忆。6. 最后分享几个我踩过的坑和现在的刷题习惯三题都 AC 之后我做了一件事把三份代码从编辑器里删掉过了三天用笔在纸上重新手写一遍。这一遍暴露了很多问题——螺旋矩阵的 if 判断漏写、删除链表的 prev 移动时机想反、设计链表 addAtIndex 的 index 边界写成了“大于等于 size”。这些问题在 IDE 里因为有编译器和报错的保护会被掩盖纯手写时逻辑就必须全部在脑子里跑通。另外一个习惯是每道题写完后强制自己用三组边界用例验证。螺旋矩阵用 1×5 和 5×1移除链表元素用“头节点全部要删”和“全链无目标值”设计链表用 addAtIndex(0)、addAtIndex(size)、deleteAtIndex(size - 1) 这些端点。跑完这些边界用例代码就算稳了。三道题难度都不高但它们是两道数据结构大门的门把手。把这三个把手拧顺了后面刷树的遍历、图的 DFS/BFS思维上都会顺很多。毕竟数据结构这东西底层的“指针怎么走、边界怎么管、状态怎么维护”都是一回事。