Day 3 的链表 part01是算法训练营里让我真正开始“手熟”的一个节点。链表这个数据结构教程里常常一句话带过由节点串联而成的线性表。但真到自己上手写插入删除、处理边界条件、调 bug 时才发现“断链”“丢失后继”“空指针”这些词不只是概念而是每次运行都可能撞上的现实。这篇文章就记录我啃链表 part01 的完整过程包括链表底层逻辑、增删改查的实操思路、踩坑复盘以及当天能动手做的三道配套题。适合正在刷算法题、学数据结构、对链表还似懂非懂的读者。1. 链表到底是什么先弄懂存储结构再谈操作技巧1.1 内存布局差别数组是一排连号座位链表是驿站接力很多人在初学阶段没搞明白一件事数组和链表的差别本质不是“有没有指针”而是数据在内存里的存放方式。数组是连续内存空间就像电影院里的连号座位1号旁边必然是2号CPU 拿到首地址后可以按偏移量直接算出来第 i 个元素在哪个位置所以随机访问是 O(1)。但代价也很明显在中间插入一个元素后面的所有元素都要统一往后挪一位删除同理后面所有元素都要往前补位。更麻烦的是数组扩容当容量不够时要重新申请一块更大的连续空间再把老数据整体搬过去这个成本在数据量大的时候非常疼。链表则完全换了一种思路。它的每个节点可以散落在内存任意位置节点里除了存数据还额外存一个指针或叫引用记录“下一个节点住哪”。就像古代驿站接力马不用一次性跑完全程每个驿站知道下一站在哪就行。这个设计带来两个关键变化插入和删除只需要调整指针指向不需要挪动数据在已知前驱节点的情况下是 O(1)数据可以零散存放不需要一整块连续空间空间利用率更灵活。但也得付出代价想找第 k 个节点必须从头开始一个个往下走随机访问是 O(n)。工程里没有银弹选择链表还是数组本质是选“访问频率高”还是“增删频率高”。1.2 节点与指针不要把它想成盒子而是便签纸和地址链表的节点长什么样其实很简单。用 Python 写也就是一个类两个字段class ListNode: def __init__(self, val0, nextNone): self.val val self.next next用 C/C 写就是一个结构体struct ListNode { int val; struct ListNode *next; };关键在于理解next存的是什么。它不是“下一个节点的完整内容”而是下一个节点所在的位置。在 Python 里叫引用在 C/C 里叫指针本质上都是“告诉你去哪找下一个节点”的地址信息。最后一个节点的next指向空即None或NULL表示“接力到此结束”。为什么我说不要把它想成一个盒子装另一个盒子因为很多人初学时会误以为链表的节点是嵌套的其实每个节点只负责两件事保存自己的值记住下一个节点的坐标。链表的遍历过程就是一个不断“取当前节点值再顺着坐标跳到下一个”的过程。1.3 复杂度对比一张表看清数组和单链表的能力边界操作数组单链表随机访问第 i 个元素O(1)O(n)头部插入/删除O(n)需要整体搬移O(1)改头指针即可尾部插入O(1) 摊还扩容时 O(n)有尾指针时 O(1)否则 O(n)指定位置插入/删除O(n)主要是搬移代价O(n)主要是找前驱的时间空间分配方式连续内存易碎片化零散内存每个节点多存一个指针这张表对后面的刷题非常重要。你会发现链表题目里大量操作都是“找到前驱节点”因为无论是插入还是删除真正麻烦的都不是改指针那一下而是找到该改哪个节点。理解这一点后面看到“双指针”“哨兵节点”才有基础。2. 手写单链表从建表到增删改查的完整实操2.1 建链表的两条路线头插法很快但我更推荐先练尾插法链表最基础的操作是“建表”就是把一组数据逐个串成一个链表。常见的构建方式有两种头插法和尾插法。头插法的逻辑是每来一个新节点就让它成为新的头节点原链表跟在它后面。def build_by_head(nodes): head None for x in nodes: new_node ListNode(x) new_node.next head # 新节点指向旧头 head new_node # 更新头指针 return head头插法确实快每次都是 O(1)不需要遍历找尾巴。但问题是最终得到的链表顺序是反的输入 [1,2,3]输出是 3→2→1。有些场景比如栈正好需要这种逆序效果但如果你想让链表保持输入顺序头插法还得最后 D 一次反转多此一举。尾插法的逻辑更贴近直觉得新节点接在链表末尾。def build_by_tail(nodes): head None tail None for x in nodes: node ListNode(x) if head is None: head tail node else: tail.next node tail node return head注意这里面有个小设计维护一个尾指针tail让“找尾部”从 O(n) 降到 O(1)。如果每次插入都从头遍历到末尾建一个 n 节点链表的时间复杂度就变成 O(n²)这在训练营练习时还好在真实工程里是不能接受的。我给新手的建议是先掌握尾插法。因为算法题里经常要求保持原有顺序尾插是默认操作等你对“指针怎么移动”有感觉了再回头玩头插法会更容易理解两者的区别。2.2 遍历输出循环里最容易写错的是“忘了移动指针”链表遍历是几乎所有链表题的基础。逻辑很简单从头节点开始只要当前节点不为空就输出它的值然后往前走一步。def print_list(head): cur head while cur is not None: print(cur.val, end ) cur cur.next print()这段代码看起来简单但我在训练营第一天写的时候犯过一个特别低级的错打印完 val 之后忘了写cur cur.next结果程序在第一个节点上无限循环控制台疯狂刷同一个数字。事后复盘问题就出在我把“输出”和“移动到下一个节点”想成了两件独立的事但在链表的循环里指针移动必须和业务操作同步发生漏掉任何一个都会出大事。另一个常见变体是while 循环条件写错。有人图省事写成while cur.next is not None这会导致尾节点永远不会被访问到输出少一个元素。记住一条配套原则需要“按节点处理”就用while cur is not None需要“看后面还有没有节点”就用while cur and cur.next具体看业务需求但默认情况下用前者最安全。2.3 插入与删除所有边界条件都来自三个特殊位置链表增删操作的“坑”其实高度集中无非就是头节点、尾节点、中间节点这三个位置处理方式不一样。只要分别把这三个边界想清楚链表操作基本就稳了。先说插入。假设要在某个值为 target 的节点之后插入一个new_node核心动作是两个指针赋值new_node.next cur.next # 先让新节点指向后继 cur.next new_node # 再让前驱指向新节点这两行代码的顺序极其讲究。我见过很多人犯过同一个错误先把cur.next改成new_node然后再去设置new_node.next cur.next结果这时候cur.next已经是new_node自己了new_node.next指向自己链表原地生成一个环。正确理解是要先接好新节点的“出边”再改前驱的“入边”。后修改前驱next因为前驱的 next 是唯一的“线索”一改就丢新节点的后继必须在丢线索之前取到。再说删除。删除某个节点本质上就是“让它的前驱跳过它直接指向它的后继”。prev.next cur.next思路一句话就能说完但有个前提你得先知道前驱节点prev是谁。这就是链表题目喜欢用双指针的原因一个负责走一个负责记录前驱。如果删除的是头节点呢头节点没有前驱这时要单独处理head head.next。这个特殊分支很容易被忽略尤其是测试数据恰好先删头节点时一跑就崩。为了彻底回避“头节点特殊处理”的烦恼算法里引入了哨兵节点我下面专门讲。2.4 哨兵节点 dummy让头节点也享受“统一待遇”哨兵节点的思路非常朴实在真正头节点前多加一个不存有效数据的占位节点让原本没有前驱的头节点也有了一个稳定的前驱。dummy ListNode(nexthead) pre dummy cur head while cur: if cur.val target: pre.next cur.next break pre cur cur cur.next head dummy.next这样在处理删除时所有节点包括原来的头节点的删除逻辑就统一了都是让pre.next越过cur。不用再单独考虑if pre is None的分支代码少了条件判断也就少了一个出错面。我一直觉得哨兵节点是链表入门阶段性价比最高的技巧因为它把“头疼的头节点”从问题里抹掉了。后面刷 LeetCode 的时候会发现几乎所有链表题的官方题解都会优先用 dummy原因就在这里。3. 链表试炼中的三大翻车现场复盘与排查3.1 断链事故先修改指向的经典错误链表题里最经典的翻车现场就是“链断了”。断链的本质是你只改了某个节点的next但没有同时安排好原来的后续节点导致一部分节点“掉在地上”访问不到。举一个我在训练营里亲眼看到的例子。有人实现插入操作写完pre.next new_node然后忘了把new_node.next指向原来的后继链表直接从中间断成两截后半段丢了。还有人反过来先执行new_node.next pre.next但此时pre.next已经被他提前改成别的东西了于是new_node连到了一个错误的位置。这两类错误的共同根源都是没有想清楚指针之间的依赖关系。我后来给自己定的规矩是任何涉及next连续修改的操作都先在心里画一条依赖链——新节点的 next 依赖于旧前驱的 next所以必须在新前驱被改之前取到旧值。简单说就是“先连新再断旧”。3.2 空指针与遍历条件NoneType 报错几乎躲不掉在 Python 里最常见的报错是AttributeError: NoneType object has no attribute val。出现这个错误含义其实只有一个你访问了一个不存在的节点。最典型的原因是while 循环条件写成cur.next is not None但 cur 本身有可能已经是 None。比如遍历到最后一个节点cur指向尾节点此时cur.next是 None循环条件不成立退出循环看起来挺正常。可如果你在循环体内先用了cur.val再判断cur.next一旦 cur 为 None程序就炸了。另一个常见场景是删除操作中匹配条件已经写成了while cur但在循环体内部没有判断cur.next是否为空就直接cur.next.val一样会炸。我的经验是链表题里凡是访问节点属性都要先确认这个节点不是 None。判断顺序也有讲究while cur and cur.next这种写法短路逻辑保证了先检查 cur 不为空再检查 cur.next 不为空安全性最好。初学者往往漏掉cur这个前置条件只记得cur.next这是空指针报错的高发区。3.3 通用排查三板斧画图、打印、缩小数据量链表调试和别的代码调试不一样它的难点在于你看不到整个链表结构只能看到一个个孤立节点。我给同组同学分享过三个排查步骤实测下来非常管用。第一动手画图。任何链表 bug都先把链表的几个关键指针head、pre、cur、next画在纸上每执行一行代码就更新一次指针位置。你会发现很多所谓的“诡异问题”画着画着就暴露了比如插入顺序不对导致成环画一遍就能看出来。第二打印轨迹。在关键位置加print输出指针当前的值在 Python 里可以打印节点对象或者在 C 里打印指针地址。打印节点值也可以但打印地址更能看出“谁指向谁”。常见做法是打印pre.val、cur.val、cur.next是否为空跑一遍就能定位问题出在哪次移动。第三缩小数据量。用空链表、单节点、两个节点这样的小用例反复测。链表的很多边界问题在数据量大的时候很难看穿但缩小到几个节点后每一步操作都清晰可见。我通常会把测试用例固定成空链表、只有头节点、两个节点删除头节点、两个节点删除尾节点、删除不存在的元素。这五组跑通了代码基本能过。我把常见问题整理成了一张速查表方便快速定位问题现象大概率原因处理建议输出少了尾节点while 条件用了cur.next改成while cur is not None输出死循环循环体里忘了移动 cur检查每个分支是否都有cur cur.next插入后出现环先改了前驱的 next 再设新节点 next先new.next cur.next再cur.next new删除后链表少一段没保留 cur.next 就把 pre 指向它先temp cur.next或直接pre.next cur.nextNoneType 报错cur 本身为 None 仍访问属性用while cur and cur.next做短路判断4. 配套实战part01 当晚能动手的三道链表题4.1 哨兵节点的威力移除链表元素LeetCode 203这道题的任务是给定一个链表头节点head和一个整数val删除链表中所有值等于val的节点。对刚学完链表基础的人来说这是最合适的第一道实战题因为它专门考察“遍历 前驱 删除”这套基本功。核心思路就是我在 2.4 里写的哨兵节点写法。创建dummy ListNode(nexthead)然后pre从 dummy 出发cur从头节点出发遍历整个链表。如果cur.val等于 val就让pre.next cur.next当前节点被“跳过”否则正常把pre移动到cur。最后返回dummy.next。时间复杂度 O(n)空间复杂度 O(1)。这道题拿它练手最大的收获不是“会写了”而是真正理解为什么要用 dummy 来统一头节点和普通节点的删除逻辑。写完这题再回头看自己之前处理头节点那个特殊的if分支你会明白朴素写法虽然也能过但代码丑且容易漏。4.2 综合题设计链表LeetCode 707如果说 203 是一次单项训练那 707 就是一次“全家桶”。它要求你实现一个链表类包含五个方法get(index)获取第 index 个节点的值addAtHead(val)头部插入addAtTail(val)尾部插入addAtIndex(index, val)指定位置插入deleteAtIndex(index)删除指定位置节点。这道题相当于把 part01 学到的所有操作都串起来了而且比单纯写函数更有挑战因为它要求你自己维护size长度变量还要处理索引越界的判断。我特别推荐这道题是因为它能暴露你对边界条件的掌握程度。几个容易翻车的点一是addAtIndex的索引范围当 index 等于链表长度时允许尾部追加当 index 大于长度时不允许操作二是deleteAtIndex删除时要先判断 index 是否有效三是头插和尾插都可以复用addAtIndex的逻辑但不要为了复用而忽略各自的特殊处理。这道题我没有看答案纯手写前后花了快四十分钟前三次提交都有边界问题但调过之后心里对链表的把握感明显上升了一个台阶。建议设计链表这道题别急着看题解先自己硬写。写不出来也没关系卡住的地方就是你链表基础最薄弱的地方比翻十遍书都管用。4.3 给下一课留个引子合并两个有序链表LeetCode 21这一题在训练营里通常排在 Day 3 的进阶区我把它放在这里更多是想给 part02 做个铺垫。题目要求输入两个升序链表把它们合并成一个新的升序链表并返回。思路其实不复杂同时用两个指针l1和l2分别指向两个链表头部比较当前两个节点的值谁小就把谁接到新链表后面然后移动对应的指针。循环结束的条件是其中一个链表走完了此时剩下的部分直接接上即可。但真正动手写会发现一个有意思的事合并操作频繁用到“把某个节点接到结果链表尾部”这正是尾插法的现场应用。你会发现只要尾插法基础打牢了这道题的主循环写起来很像是在用两个输入链表“喂”一条新的链表。反转链表、环形链表这类更经典的题目在 part02 会系统展开这里不展开写。但如果你今晚有空不妨先自己想一个问题在不借助额外数组的情况下怎么把链表每个节点的 next 指向前一个节点带着这个问题进入下一课你会学得轻松很多。5. 学习方法与下一步路线链表 part01 之后怎么练5.1 画图比写代码先一步链表题最忌讳的就是盯着屏幕硬想。我的习惯是拿到题目先画链表画出head、pre、cur、next这几个关键角色再标出每一步操作后指针的移动方向。尤其是需要同时操作两个指针的题目比如删除指定节点、反转链表画图能让你一眼看出指针的依赖关系避免“先断后连”的老毛病。有同学问过我画图是不是太浪费时间我的回答是前期画图确实慢但对建立“指针感”特别有好处。等画图熟练了许多链表题你甚至不用真画脑海里就能模拟出指针变化的轨迹这时候你的速度自然就上来了。训练营里的节奏是“先画十道再写十道”亲测有效。5.2 用三个问题做自我检查Day 3 结束前我建议你问自己三个问题第一能否在 30 秒内写出链表的节点类和遍历函数这个要求看起来很简单但真动手会有很多人卡壳特别是节点类的__init__参数顺序、遍历时的循环条件。第二能否在一分钟内说清楚插入、删除的边界条件这里说的不是背书而是针对“头插、尾插、指定位置插入”和“删头、删尾、删中间”六种情况分别给出正确的操作步骤。第三能否不看笔记写一遍带哨兵节点的删除操作如果这一步还要翻笔记说明 dummy 的思想还没真正内化建议再多做两道题巩固。这三个问题都过关链表 part01 就算真正吃透了可以放心进入反转链表那一课。最后说一点个人感受。链表是我学算法以来第一个觉得“看懂了但不一定会写”的知识点它特别考验手感和细心没有捷径。但也是从链表开始我才真正体会到算法训练的意义不是背代码而是靠一次次跑偏、调错、画图把每一步操作变成肌肉记忆。希望这份记录能帮同样卡在链表初期的你少踩几个坑。