1. 链表是什么先从数组的痛点说起很多刚学数据结构的朋友会有个疑问既然Python里已经有了list为什么还要搞链表这问题我当年也问过。等你真正拿Python写底层一点的东西——比如缓存淘汰策略、操作系统的进程队列、音乐播放器的播放列表——就会发现list这种看起来万能的容器其实有它的天花板。Python的list底层是动态数组说白了就是一块连续的内存。连续内存的好处是随机访问快list[i]直接靠偏移量算地址O(1)时间就能拿到元素。但坏处也很明显插入/删除靠后位置还好一旦在头部或中间插入、删除后面所有元素都要整体搬移最坏O(n)。扩容有开销list装满了要重新申请一块更大的内存把旧数据拷过去如果频繁在头部插入性能会很难看。链表解决的就是这个问题。它的核心思想极其朴素不要求内存连续每个节点不光存数据还存一个下一个节点在哪儿的引用Python里就是普通的对象引用。你要在中间插入一个节点不需要挪动任何元素只需要改两条引用关系O(1)时间搞定。代价是你要找一个元素得从头往后挨个找随机访问退化成O(n)。打个比方数组是电影院里的连座票座位编号固定找第8排直接看排号就行链表是玩寻宝游戏或者驿站传信你只知道手上这一站的下一个驿站叫什么想知道第8个驿站长什么样只能一站一站跑过去。这个设计哲学贯穿整个数据结构这门课没有完美的数据结构只有适合当前场景的数据结构。数组适合读多写少链表适合写多读少。而在Python里学链表还有一个额外的好处——Python的变量赋值本质是引用绑定后面我会细讲学了链表你对引用对象内存模型的理解会上一个台阶而这个理解能力在刷LeetCode、读源码、做系统设计时都是必备的。链表这个主题下面还有一堆变体单链表、双向链表、循环链表、带头节点的链表、不带头节点的链表。不同教材的术语还不太一样但核心代码你吃透一套其他都是换汤不换药。本文我选Python来实现因为Python写链表有个天然优势不需要手动管理内存也不用被C/C那套指针语法绕晕能把注意力完全放在节点之间的引用关系上。你完全可以用它当跳板看懂之后回头再看C版、Java版的链表实现会觉得异常轻松。2. 手写一个单链表核心操作拆解单链表是最基础的形态。一个节点有data和next两个属性data存值next指向下一个节点。最后一个节点的next是None表示链表到头了。2.1 节点类和链表类的设计先写节点类Python里最直白的方式class Node: 链表节点 def __init__(self, data): self.data data self.next None def __repr__(self): return fNode({self.data})然后写链表类。这里第一个设计决策就来了要不要维护头节点head对于单链表来说head是唯一的入口所有操作都从它开始所以必须存。额外的我建议再维护一个tail尾节点引用这样尾插法能达到O(1)不然每次尾插都要遍历到最后一个节点白费了链表插入快的优势。class LinkedList: def __init__(self): self.head None self.tail None self.size 0size这个变量也是我自己加的实际工程偏好。算法题里你能O(1)拿到链表长度会省很多事。比如后面讲找中间节点有size的话可以直接算没有就得靠快慢指针。两者都能解但有size在某些场景下更快。这里还有第二个设计决策要不要带虚拟头节点dummy head这是个非常重要的技巧。如果你不带头节点空链表和非空链表的插入逻辑是两套代码空链表要把head指到新节点非空链表只需要改next。写起来容易漏也容易写出越界问题。带一个虚拟头节点它永远存在head永远不为空所有插入删除逻辑就可以统一写。代价是遍历的时候要从dummy.next开始稍微绕一点。我个人的习惯是算法题里用虚拟头节点少踩坑工程代码里看场景省一个节点的内存没啥意义主要是看团队的代码风格。2.2 头插法和尾插法头插法把新节点插在链表最前面def prepend(self, data): 头插法O(1) new_node Node(data) # 先把新节点指向原本的head new_node.next self.head # 再把head指向新节点 self.head new_node注意这两行的顺序极其重要。如果你先写了self.head new_node新节点的next指向谁这时候self.head已经是新节点自己了new_node.next self.head等于指向了自己形成一个环链表就断了。 **先改新节点的next再改头指针**这个顺序我建议你刻在DNA里后面讲反转链表还会再遇到一次。尾插法把新节点接在链表末尾def append(self, data): 尾插法维护tail后为O(1) new_node Node(data) if self.head is None: self.head new_node self.tail new_node else: self.tail.next new_node self.tail new_node self.size 1如果不维护tail这里就得从头遍历找到最后一个节点。遍历的代码是这样def _get_last_node(self): if self.head is None: return None cur self.head while cur.next is not None: cur cur.next return cur注意这个while cur.next is not None的条件它找到的是最后一个节点而不是None。很多人初学的时候写成while cur is not None结果返回的是None白白把最后一个节点弄丢了。这个细节在链表里太常见了你要找最后一个节点就应该在cur.next is None时停下你要遍历所有节点才允许cur跑到None。2.3 遍历与查找遍历整个链表def traverse(self): 遍历链表返回一个列表方便观察 result [] cur self.head while cur is not None: result.append(cur.data) cur cur.next return result这里的循环条件和上面完全相反正因为如此你遍历完之后cur一定会变成None正好印证了链表最后一个节点指向None这个抽象模型。按值查找第一个匹配的节点def find(self, value): cur self.head while cur is not None: if cur.data value: return cur cur cur.next return None按索引查找第i个节点记住链表没有随机访问只能数着走def get(self, index): if index 0 or index self.size: raise IndexError(index out of range) cur self.head for _ in range(index): cur cur.next return cur这里体现了链表和数组最本质的性能差异数组arr[5]是O(1)链表list.get(5)是O(n)。LeetCode上的链表题动不动就提示你能否用O(1)空间解决就是在考验你如何利用引用关系去省掉这些不必要的遍历。2.4 指定位置的插入与删除在索引index处插入节点这是单链表操作的重头戏。关键在于你找到了第index-1个节点前驱节点然后改两条引用。def insert(self, index, data): 在指定位置插入节点 if index 0 or index self.size: raise IndexError(index out of range) if index 0: self.prepend(data) return if index self.size: self.append(data) return new_node Node(data) # 找到前驱节点即第 index-1 个节点 prev self.get(index - 1) # 先把新节点指向 prev 原本的下一个 new_node.next prev.next # 再把 prev 指向新节点 prev.next new_node self.size 1注意这里如果只用get(index)拿到第index个节点你是插不进去的因为单链表往前找不到前驱。所以要插入必须拿到前驱节点。这算是单链表一个很烦人的特点它只支持向后查找删除和插入都依赖前驱。这也是为什么实际场景里有那么多双向链表——双向链表往前也能走删除节点就不需要单独找前驱了。删除指定位置的节点同样需要前驱节点def delete(self, index): 删除指定位置的节点 if index 0 or index self.size: raise IndexError(index out of range) if index 0: # 删除头节点 self.head self.head.next if self.head is None: self.tail None self.size - 1 return prev self.get(index - 1) removed prev.next # 被删节点 prev.next removed.next # 前驱直接跳过被删节点 if removed self.tail: # 删的是尾节点 self.tail prev self.size - 1这里面有个很容易被忽视的坑删尾节点时tail要回退到前驱节点。如果你不维护tail这一段可以省但你既然维护了就得在删除时同步处理好。我在实际写的时候还踩过一个更隐蔽的坑当链表只有一个节点时删除后head和tail都应该是None上面的代码里self.head self.head.next之后head变成Nonetail也被置为None没问题。但如果链表只有一个节点而你走的是index 0分支且你忘了处理tail后面的尾插就会因为tail指向一个已被孤立的节点而出bug而且这种bug非常难追踪因为它不会立刻报错而是要到下一次操作才炸。3. 链表逆序面试高频题的两种解法与思考链表逆序反转是面试基础题几乎每家公司的题库里都有。热搜词里也出现了python单链表逆序链表遍历这种关键词说明这是学习链表时绕不开的一个坎。逆序的难点不在语法而在你能否在脑子里清晰维护三根指针的关系。3.1 迭代法三指针维护迭代法的思路遍历链表的过程中逐个把每个节点的next指向它的前驱。需要一个prev指针记录当前节点的前驱一个cur指针记录当前节点再加一个temp保存cur.next防止改完引用后找不到后面的路。def reverse(self): 迭代反转链表O(n)时间O(1)空间 prev None cur self.head while cur is not None: temp cur.next # 先保存next否则改完引用就丢了 cur.next prev # 当前节点指向前驱 prev cur # 前驱后移 cur temp # 当前节点后移 self.head prev # 最后prev就是原链表的尾节点即新链表的头这个代码建议你亲手画一遍指针变化图尤其是prev cur和cur temp这两步的顺序它们的先后决定了你能不能走动起来。画图的过程就是用纸笔模拟一个微型状态机多模拟几次以后撸任何链表题都顺。3.2 递归法理解子问题的视角递归版本在面试里也经常被问到它考察的不是你会不会用递归而是你懂不懂链表本身是递归定义的一个链表可以看成一个节点 一个更短的链表。def reverse_recursive(self, node): 递归反转链表返回新链表的头节点 if node is None or node.next is None: return node new_head self.reverse_recursive(node.next) # 核心让下一个节点反过来指向当前节点 node.next.next node node.next None return new_head这段代码初看会让人懵。我拆解一下假设链表是1 - 2 - 3 - 4 - None递归到最深处会停在节点4因为4.next is None返回4。回溯到节点3时node 3node.next是4于是node.next.next node等价于4.next 3也就是把4的指针掰回去指向3然后node.next None把3的旧链接断开。这样4和3就形成了一个反向的4 - 3。继续回溯2会把3掰回来最终得到一个完整的反转链表。递归法的时间复杂度是O(n)空间复杂度是O(n)——因为递归会占用调用栈。所以如果用递归法实现了反转在LeetCode上提交的时候空间复杂度往往会被标成O(n)。面试官要是问你能否用O(1)空间实现你就要掏出迭代法。这两者是相辅相成的递归版展现了分治思维迭代版展现了指针操作能力。3.3 实测对比与经验我用一个100万节点的链表做过简单对比Python 3.10普通笔记本方法耗时额外空间迭代法约0.08秒O(1)递归法约0.12秒O(n)调用栈差距没有特别大但递归法在链表节点数超过Python的递归深度限制默认1000层时会直接抛出RecursionError。所以生产环境或大链表场景优先用迭代法面试时先讲递归法展示思路再切换到迭代法展示优化能力这套组合拳很加分。还有一个反转操作的细节反转之后原来的head变成了tail原来的tail变成了head。如果你维护了tail字段反转完需要交换头尾引用不然后续用append会出问题。我自己就栽过这个跟头在写一个LRU缓存的时候反转完忘了更新tail结果整个链从尾巴上又长了一截新的完全乱套。4. 快慢指针链表进阶题的万能钥匙链表里有一类进阶问题靠单纯遍历不好解但如果用快慢指针两个指针一个每次走两步一个每次走一步很多问题变得极其优雅。这也是面试官非常爱考的思维模型。4.1 为什么快慢指针能追上先讲数学原理。假设慢指针速度为一步/轮快指针为两步/轮两者同时从头节点出发。如果有环快指针先进入环慢指针随后进入。环内快指针相对于慢指针的速度差是1步/轮所以它俩之间的距离会逐步缩短最终一定会相遇。这就好比两个人在圆形跑道上跑步快的人每圈都会追上慢的人一次前提是跑道是闭合的。如果链表没有环快指针会先一步到达None循环自然结束。def has_cycle(self): 检测链表是否有环Floyd判圈算法 slow self.head fast self.head while fast is not None and fast.next is not None: slow slow.next # 慢指针走一步 fast fast.next.next # 快指针走两步 if slow is fast: return True return False一个常见错误是循环条件写成while fast is not None但fast.next可能是None你再去访问fast.next.next就炸了。所以条件里必须同时检查fast和fast.next。4.2 找到环的入口进阶版是找到环形链表的入口节点。Floyd算法有个很妙的结论快慢指针第一次相遇后把其中一个指针放回头节点两个指针都改成一次走一步下一次相遇的位置就是环入口。这个结论可以用数学推导但记住结论做面试题就够了。def detect_cycle_start(self): slow self.head fast self.head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow is fast: # 相遇了把slow放回头节点fast保持在相遇点各走一步 slow self.head while slow is not fast: slow slow.next fast fast.next return slow return None4.3 找到中间节点和倒数第k个节点快慢指针还能用来找中间节点快指针到终点时慢指针正好在一半位置。这比先遍历一遍数长度、再走一半更简洁也省一次遍历。def find_middle(self): if self.head is None: return None slow self.head fast self.head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next return slow找倒数第k个节点思路是双指针保持固定距离快指针先走k步然后快慢指针一起走快指针到底时慢指针正好在倒数第k个节点。def find_from_end(self, k): 返回倒数第k个节点k从1开始计数 if k 0: return None fast self.head slow self.head # 快指针先走k步 for _ in range(k): if fast is None: return None # k超过了链表长度 fast fast.next # 快慢一起走 while fast is not None: fast fast.next slow slow.next return slow这几道题练下来你会发现快慢指针本身就是用空间换时间的反面——它不申请额外空间而是用时间差制造信息差。哪根指针该快、哪根该慢、出发点在哪全是围绕距离和速度在推演做题的时候思路一定要在纸上先模拟一遍。5. 变体循环链表与双向链表单链表只是起点。实际工程里更常用的是循环链表和双向链表它们解决了单链表的一些天然缺陷。5.1 循环链表约瑟夫环问题循环链表就是把最后一个节点的next指回头节点整个链表变成闭环。它最大的好处是从任意一个节点出发都能遍历整个链表。经典应用是约瑟夫环问题一群人围成圈报数每报到指定数字就出圈问最后剩下的是谁。class CircularLinkedList: 循环链表tail.next 指向 head def __init__(self): self.head None self.tail None def append(self, data): node Node(data) if self.head is None: self.head node self.tail node node.next node # 自己指向自己形成环 else: node.next self.head self.tail.next node self.tail node约瑟夫环的模拟过程核心就是边遍历边删除而删除一个循环链表中的节点时尾节点的处理比单链表简单——因为它永远指向头节点不会因为删除而变成None代码逻辑反而更统一。如果你想练手可以写一个josephus(n, k)函数用循环链表模拟报数出圈这和LeetCode上的约瑟夫环题一样练做完你对循环链表的理解会非常扎实。5.2 双向链表从只能向后到可以前进双向链表的每个节点有prev和next两个指针class DoublyNode: def __init__(self, data): self.data data self.prev None self.next None双向链表最大的价值在于删除任意节点时不需要找前驱。在单链表里你要删节点必须从头遍历找到它的前驱双向链表直接通过node.prev就能拿到前驱删除操作变成O(1)。这个特性让双向链表成为实现LRU缓存最近最少使用的首选结构。常见的缓存淘汰策略就是用一个双向链表哈希表哈希表O(1)定位节点双向链表O(1)删除和移动节点完美互补。用Python写一个最简LRU骨架你可以把链表操作串起来看class LRUCache: def __init__(self, capacity): self.capacity capacity self.dict {} # key - DoublyNode self.head DoublyNode(0, 0) # 虚拟头 self.tail DoublyNode(0, 0) # 虚拟尾 self.head.next self.tail self.tail.prev self.head def _remove(self, node): node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): # 把节点插到虚拟头之后 node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node这段代码里那个虚拟头虚拟尾的设计非常典型它消灭了所有空链表只有一个节点的特殊情况。链表插入删除的代码一旦写出一堆if分支八成是你没有用好虚拟节点这个技巧。5.3 为什么面试总爱考链表变体我把链表变体总结成一张小表方便你复习时对照类型指针数量尾节点指向核心优势典型应用单链表1nextNone结构最简单省内存邻接表、多项式运算循环链表1next头节点可以从任意节点遍历全部约瑟夫环、轮转调度双向链表2prev, nextNone删除任意节点O(1)LRU缓存、编辑器undo双向循环链表2prev, next头节点前后都可遍历且成环音视频播放列表面试考链表变体其实是在考察你对引用关系的操控能力。所谓数据结构与算法数据的组织方式决定了算法的复杂度链表就是这句话最直接的体现。6. 避坑指南引用、空指针和边界条件链表题写起来代码不长但错误率极高。我总结了自己踩过和看过别人踩过的几类坑单独列一节讲希望你能少走弯路。6.1 空链表的处理链表为空时head和tail都是None。很多操作首先要判断自己是不是在空链表上操作遍历while cur is not None自然处理空链表直接不进入循环。插入空链表的头插和尾插head和tail要同时指向新节点。删除空链表不能删除要抛异常或返回None。查找空链表直接返回None。另外一点写链表代码时能不访问.next就不访问。比如cur.next.next这类级联访问在cur.next为None的情况下会抛AttributeError。LeetCode提交时报错AttributeError: NoneType object has no attribute next十有八九就是这个原因。6.2 Python引用的陷阱这是Python特有的坑。Python里所有变量都是引用所以写prev cur的时候prev和cur指向同一个对象。如果你以为这是复制了一份后面改prev的时候会把cur也改了。尤其是写链表反转、合并这类需要频繁移动指针的代码必须时刻清楚你操作的到底是哪个节点对象还是仅仅是把引用换了个名字。举个典型例子a Node(1) b a # b 和 a 指向同一个节点 b.data 99 # 同时修改了 a.data print(a.data) # 99链表里大量存在这种引用共享关系这既是Python好写链表的原因天然支持引用也是新手容易懵的地方。建议初学者在做链表题时在纸上画出每个指针指向的内存对象而不是只画箭头能有效避免这个坑。6.3 边界条件的三个必查位置链表题的bug至少有七成出在边界条件上。每次写完代码建议立刻检查这三个位置空链表操作前后head、tail是否为None只有一个节点删除后链表应为空反转后head和tail互换头尾节点插入删除在头部和尾部时链表类维护的属性head、tail、size是否同步更新举个具体例子删除最后一个节点时如果只写了prev.next removed.next而忘了把self.tail更新为prev那么tail就指向一个已经被孤立的节点。后续任何基于tail的操作比如尾插都会把新节点挂到一个幽灵节点上链表从逻辑上就断了调试起来非常痛苦。还有一个小经验如果你用链表实现队列一定要搞清楚你用的是头插尾删还是尾插头删。队列是FIFO从哪头进从哪头出必须统一。我之前就用单链表实现队列时贪图简单把头插和尾删混用结果整个队列的顺序反了排查了半天才发现是入队出队方向不一致。7. 实战练习题目与扩展建议我自己练链表时用的题目清单按难度递增列一下供你参考。建议每道题都先手画链表图再写代码最后跑测试用例。难度题目核心考点基础反转单链表迭代/递归指针操作基础删除链表节点前驱节点处理中等环形链表判断快慢指针中等两个有序链表合并虚拟头节点中等删除倒数第N个节点双指针法进阶LRU缓存双向链表哈希表进阶约瑟夫环循环链表其中两个有序链表合并特别能检验虚拟头节点的掌握程度def merge_two_lists(l1, l2): dummy Node(0) # 虚拟头 cur dummy while l1 is not None and l2 is not None: if l1.data l2.data: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next # 剩下的直接接上 cur.next l1 if l1 is not None else l2 return dummy.next # 返回真实头节点dummy在这里就是整个合并过程的锚点你不用再单独判断第一个节点到底接l1还是l2全都能统一处理。最后返回dummy.next这个模式在链表题里出现的频率非常高。扩展方向上学完链表可以往几个方向走用链表实现更复杂的数据结构栈、队列、哈希表的链式实现链表与树的关联二叉树也可以用左指针右指针的节点模型来定义理解了链表节点二叉树的节点理解就顺理成章了并查集、邻接表图的存储常依赖链表或链表思想数据结构408、考研机试里都有涉及Python内置模块参考collections.deque底层就是双向链表实现的可以用来对比Python帮你封装好的数据结构和你手写的数据结构之间的异同我个人练链表的方法很简单别光看拿笔在纸上画然后上手敲敲完再故意破坏一点条件看报错最后总结成自己的小抄。这个东西不练个二三十遍指针的直觉是出不来的。最后分享一个实战中的小技巧调试链表代码时在关键节点处加一个辅助函数把当前链表现状打出来比如打印[head] - 1 - 2 - 3 - [tail]比空想和用debugger断点都要直观。很多时候看着打印结果走一遍bug原因一眼就出来了。