1. 链表怎么就“火”了这两年不管是面试造火箭还是业务拧螺丝链表永远是数据结构里绕不开的一道坎。链表这种东西背概念容易真要手写实现、分析性能、处理边界情况翻车的人一抓一大把。我身边不少朋友在准备面试时链表题刷了一遍又一遍可一到“请用Python实现一个双向链表并支持在指定位置插入”这种题还是会卡壳。先说清楚这篇文章要讲什么链表的核心概念、内存布局、Python代码实现单链表和双链表都写以及面试和工程里最常见的几个操作和坑点。适合这么几类人看正在准备算法面试的开发者、初学数据结构的学生、以及在业务里需要用Python做底层数据存储优化的工程师。我会尽可能把链表讲的接地气一点因为链表本身并不复杂复杂的是很多人一开始没理解它和数组的根本差异导致后面越学越糊。这篇文章会把那些“老师没讲透、文档没写清”的地方一次性说清楚。2. 链表的本质与内存模型2.1 数组和链表的分水岭在哪数组和链表最大的区别不是“谁快谁慢”而是它们在内存里的组织方式完全不同。数组是一块连续的内存空间就像一栋楼的房间号是连着的住103的隔壁一定是104。这种连续性带来的好处是通过下标访问任何一个元素CPU可以直接算出它的内存地址时间复杂度是O(1)。坏处也明显插入或删除一个元素后面的所有元素都要挪位置尤其是插入在头部时整个数组都得搬家。链表则完全不同。链表里的节点散落在内存各处每个节点除了存自己的数据还要额外存一个指针或者叫引用指向下一个节点的位置。就像寻宝游戏每个线索会告诉你下一个线索藏在哪里你只能一个接一个地找不能跳着找。这个差异决定了几乎所有后续行为的对错判断随机访问数组快、链表慢插入删除链表快只要你知道位置、数组慢。理解了这个分水岭后边一切分析都顺理成章。2.2 单链表的基本结构拆解单链表是最简单的链表形态。每个节点包含两部分数据域和指针域。数据域存实际数据指针域存下一个节点的地址。用Python的类来表示就是这个样子class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这段代码是整个链表世界的基石。val可以是任意Python对象next要么是None表示链表到末尾了要么是另一个ListNode。你可能会问Python里不是所有东西都是对象引用吗为什么不直接用列表还非得自己写节点类答案是Python内置的list其实是动态数组为了解决连续内存的问题Python解释器会在底层维护一个指针数组当你插入元素时依然会有元素搬移的开销。而链表用节点引用的方式彻底绕开了内存连续性要求。为了更形象一点可以想象一列火车火车头是链表头节点每节车厢是一个节点车厢之间的连接钩子就是指针域。你要找第5节车厢的人只能从火车头开始一节一节往后找没别的办法。这就是链表的遍历逻辑。2.3 带头节点和不带头节点的区别链表实现里有一个经常让人懵的细节头节点。有些实现里会单独留一个不存数据的头节点dummy head有些实现直接让头指针指向第一个实际数据节点。我用一张场景来解释两者区别不带头节点链表为空时头指针是None。插入第一个节点时要特殊处理因为head本身得指向新节点。带头节点链表为空时头指针指向一个“空壳”节点这个节点的next是None。所有插入删除操作都可以统一处理不需要判断头指针为空的情况。在面试和工程代码里我强烈推荐用dummy head虚拟头节点它能省掉大量边界条件的判断。尤其是做链表删除类操作时虚拟头节点几乎能帮你避开所有“头节点被删了咋办”的崩溃瞬间。3. Python实现单链表从零到能写能改3.1 定义节点类和链表类刚刚已经定义了ListNode现在我们把整个单链表类写出来。这个类至少得支持以下操作获取长度、判断是否为空、遍历打印、尾部添加、头部添加、指定位置插入、删除指定位置、按值查找、按索引取值。class SingleLinkedList: def __init__(self): self.head None self.size 0 def is_empty(self): return self.size 0 def length(self): return self.size def travel(self): cur self.head result [] while cur: result.append(str(cur.val)) cur cur.next return - .join(result) if result else None (empty list) def add_first(self, val): node ListNode(val) node.next self.head self.head node self.size 1 def add_last(self, val): node ListNode(val) if self.is_empty(): self.head node else: cur self.head while cur.next: cur cur.next cur.next node self.size 1 def insert(self, index, val): if index 0 or index self.size: raise IndexError(Index out of range) if index 0: self.add_first(val) return if index self.size: self.add_last(val) return node ListNode(val) cur self.head for _ in range(index - 1): cur cur.next node.next cur.next cur.next node self.size 1这几个方法写完后单链表的基本骨架就出来了。注意insert方法里的边界判断——index可以等于size表示在末尾追加index必须是非负的index为0时直接头插。3.2 遍历链表的日常操作链表的所有操作几乎都建立在遍历之上。遍历的核心逻辑就一个while循环从头节点开始只要当前节点不是None就处理数据然后让指针后移。def travel(self): cur self.head while cur: print(cur.val, end - ) cur cur.next print(None)这里要提醒新手一个容易踩的坑很多人在遍历时会不经意间修改了原来的头节点。比如有人会写cur self.head然后遍历过程中又去改cur.next甚至直接self.head self.head.next这样链表结构就被破坏了。正确做法是永远用一个临时变量cur去操作不要动self.head本身除非你确实是在做头节点删除或插入。另外遍历的退出条件一定是cur is None不是cur.next is None。很多bug来源于此。如果条件是while cur.next:那么当cur指向最后一个节点时循环会继续但此时cur.next是None循环体里再访问cur.next.next直接报错。3.3 插入操作真正理解指针怎么玩链表的插入核心操作就两行之间的顺序问题node.next cur.next cur.next node这两行的顺序不能颠倒。如果先执行cur.next node那么原来的cur.next节点就找不到了链表从这里断掉后续所有节点全部丢失。通俗点说假如你站在一个队列中间要让新来的插到你后面你得先让新来的人拉住原来你身后那个人的手再让你自己拉住新来的人。如果你先松手去拉新人原来身后的人就没人理了。我在实际教学和面试辅导中发现至少一半的人第一次写插入时都会把这两行顺序写反。这个坑一旦掉进去链表就碎成了两段。还有一点需要注意在指定位置插入时我们要找的是目标位置的前一个节点。比如要在索引2的位置插入我们需要遍历到索引1的节点然后让新节点插入它后面。很多新手会遍历到索引2结果新节点插到了索引2的后面位置偏了一位。3.4 删除操作跳过那个节点就完事了吗删除的核心逻辑更简单只有一行cur.next cur.next.next就是让前一个节点直接指向被删节点的下一个节点所谓“跳过”。Python有垃圾回收机制被跳过的节点没有引用后会被自动回收不需要像C/C那样手动free。但删除有个非常容易被忽略的坑如果要删除的是头节点self.head self.head.next就可以了这个属于特殊情况。如果链表只有一个节点删除后head变成Nonesize归零。如果你用dummy head写法这些特殊情况会少很多。删除后别忘了size减一。很多人在写插入时记得加size写删除时却忘了减。这看起来是小问题但如果你后续实现了length()方法并利用它做循环判断size不准会导致各种离奇bug——比如循环多跑一次、索引判断失效。3.5 完整可运行的单链表代码把前面几段合并再补上查找和删除指定值的代码一个能直接跑的单链表类就完整了。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class SingleLinkedList: def __init__(self): self.head None self.size 0 def is_empty(self): return self.size 0 def length(self): return self.size def add_first(self, val): node ListNode(val) node.next self.head self.head node self.size 1 def add_last(self, val): node ListNode(val) if self.is_empty(): self.head node else: cur self.head while cur.next: cur cur.next cur.next node self.size 1 def insert(self, index, val): if index 0 or index self.size: raise IndexError(Index out of range) if index 0: self.add_first(val) return if index self.size: self.add_last(val) return node ListNode(val) cur self.head for _ in range(index - 1): cur cur.next node.next cur.next cur.next node self.size 1 def delete_by_value(self, val): cur self.head prev None while cur: if cur.val val: if prev is None: self.head cur.next else: prev.next cur.next self.size - 1 return True prev cur cur cur.next return False def find(self, val): cur self.head index 0 while cur: if cur.val val: return index cur cur.next index 1 return -1 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.val def travel(self): cur self.head result [] while cur: result.append(str(cur.val)) cur cur.next return - .join(result) if result else None (empty list) if __name__ __main__: sll SingleLinkedList() sll.add_last(10) sll.add_last(20) sll.add_first(5) sll.insert(2, 15) print(sll.travel()) # 5 - 10 - 15 - 20 print(sll.find(15)) # 2 sll.delete_by_value(10) print(sll.travel()) # 5 - 15 - 20这段代码建议直接跑一遍观察输出再手动改几个用例测试边界条件。比如不断往空链表里添加删除、在头部反复插入、删除头节点、删除尾部节点等。边界条件是链表最容易出错的地方多跑多试才有效果。4. 双向链表回头也能走凭什么4.1 为什么需要prev指针单链表只能从头往尾走这带来一个非常尴尬的问题你要删除某个节点必须知道它的前驱节点是谁。如果只给定一个当前节点单链表是没法直接删除它的——你找不到它前面是谁。双向链表就是来解决这个问题的。每个节点多了一个prev指针指向它的前一个节点。这样无论从前往后还是从后往前都能遍历。代价也很明确每个节点多存一个引用内存开销上升每次插入或删除需要多维护一个prev指针代码复杂度明显上升。4.2 双向链表节点定义与完整实现class DoublyListNode: def __init__(self, val0, prevNone, nextNone): self.val val self.prev prev self.next next class DoublyLinkedList: def __init__(self): self.head None self.tail None self.size 0 def is_empty(self): return self.size 0 def length(self): return self.size def add_first(self, val): node DoublyListNode(val) if self.is_empty(): self.head node self.tail node else: node.next self.head self.head.prev node self.head node self.size 1 def add_last(self, val): node DoublyListNode(val) if self.is_empty(): self.head node self.tail node else: node.prev self.tail self.tail.next node self.tail node self.size 1 def insert(self, index, val): if index 0 or index self.size: raise IndexError(Index out of range) if index 0: self.add_first(val) return if index self.size: self.add_last(val) return node DoublyListNode(val) cur self.head for _ in range(index): cur cur.next # 在 cur 之前插入 node node.prev cur.prev node.next cur cur.prev.next node cur.prev node self.size 1 def delete_by_value(self, val): cur self.head while cur: if cur.val val: if cur.prev: cur.prev.next cur.next else: self.head cur.next if cur.next: cur.next.prev cur.prev else: self.tail cur.prev self.size - 1 return True cur cur.next return False def travel_from_head(self): cur self.head result [] while cur: result.append(str(cur.val)) cur cur.next return - .join(result) if result else None (empty list) def travel_from_tail(self): cur self.tail result [] while cur: result.append(str(cur.val)) cur cur.prev return - .join(result) if result else None (empty list)这段代码里有两个细节值得好好琢磨。第一个是insert方法里找节点的策略。我选择遍历到index位置的节点cur然后把它前面插入新节点。这样做的好处是统一处理不管插入位置在哪逻辑都一样。但前提是你必须同时维护cur.prev的指向这个四步操作改node.prev、node.next、前节点的next、cur的prev顺序不能乱。第二个是delete操作里的“双向断开”。删除一个节点时要让前一个节点的next指向后一个节点同时让后一个节点的prev指向前一个节点。漏掉任何一个都会导致双向链表的指针结构断裂。4.3 删除时最容易被忽略的双向细节我在给同事Review代码时最常看到的问题就是双向链表删除时忘了更新tail或者忘了更新某个节点的prev。尤其当删除的是中间节点时很多人的第一反应是只做prev.next cur.next完全忘了cur.next.prev cur.prev这一句。我自己的习惯是删除逻辑写完后立刻做一轮遍历检查——从head走到tail再从tail走回head确认两次遍历的结果完全一致。这个习惯帮我发现过无数次低级但致命的指针错误。双向链表的好处不仅仅是能倒着走在面试题里LRU缓存淘汰算法、浏览器的前进后退功能底层都是它在支撑。后面我会专门讲这些应用场景。5. 循环链表封口之后玩法全变了5.1 循环链表的基本概念循环链表就是把单向链表最后一个节点的next从None改成指向head形成一个环。如果要双向循环那就是tail的next指向headhead的prev指向tail。最大特点任何一个节点都能作为起点遍历完整条链表。你从任意节点出发最终都能绕回自己。但这也带来一个麻烦遍历的终止条件不再是cur is None而是“我什么时候绕回起点了”。如果循环条件判断错了基本就是个死循环程序直接卡死。5.2 用快慢指针判断链表是否有环循环链表最经典的实战场景是“判断链表是否有环”。面试里考的最多的就是快慢指针法。原理非常简单两个指针同时从head出发快指针每次走两步慢指针每次走一步。如果链表有环快指针最终会追上慢指针两个指针在环内相遇如果没有环快指针会先走到None循环自然结束。def has_cycle(head): if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False为什么要快指针走两步而不是三步四步两步是最小安全步长能保证如果存在环快指针一定能在有限步内追上慢指针不会出现跨过去的情况。三步四步虽然也能判环但可能跳过慢指针导致永远相遇不了。我之前帮一个朋友调试过一个诡异问题链表检测时快指针走了三步结果链表明明有环却返回False。排查了半天发现就是步长问题。快慢指针判环步长选2是标准答案别乱改。5.3 找到环的入口节点判环只是第一步面试进阶题通常会追问如果链表有环请找到环的入口节点。这里有一个非常漂亮的数学结论快慢指针第一次相遇后把快指针重新放回head然后快慢指针都改为每次走一步两者再次相遇的位置就是环的入口。def detect_cycle_start(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None fast head while fast is not slow: fast fast.next slow slow.next return fast这个结论的推导过程不复杂假设head到环入口距离是a环入口到第一次相遇点距离是b环一圈长度是c。快指针走的路程是慢指针的两倍相遇时快指针比慢指针多走了n圈。设慢指针走了a b快指针走了a b n*c又因为快指针速度是两倍所以a b n*c 2(a b)化简得到a n*c - b这就意味着从head走到环入口的距离a完全等于从相遇点继续走到环入口的距离。所以把快指针重置到head两指针同速前进再相遇时必然是入口。这公式我每次写都要重新推一遍但推完再用代码实现基本不会错。6. 面试和工程里高频出现的链表场景6.1 反转链表迭代与递归两种姿势反转链表是链表题里的超级经典不会写基本等于没学过链表。迭代法思路用三个指针pre前一个节点、cur当前节点、next_temp存下一个节点边走边把当前节点的next改成指向pre。def reverse_list(head): prev None cur head while cur: next_temp cur.next cur.next prev prev cur cur next_temp return prev递归法的思路则是先走到最后一个节点然后逐层返回时修改指针方向def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head有人说递归很难懂但我个人觉得递归反转链表一旦理解后就再也忘不掉了。关键在于理解head.next.next head这行它让当前节点的下一个节点反过来指向自己完成局部反转。递归的返回值是反转后链表的头也就是原本链表的尾节点。6.2 删除倒数第N个节点这个题的标准解法是双指针快指针先走n步然后快慢指针一起走当快指针到达末尾时慢指针正好指向倒数第n个节点。def remove_nth_from_end(head, n): dummy ListNode(0, head) fast dummy slow dummy for _ in range(n): fast fast.next while fast.next: fast fast.next slow slow.next slow.next slow.next.next return dummy.next这里用dummy head的好处再次体现如果要删除的是真正的第一个节点慢指针在dummy节点上也能正常执行slow.next slow.next.next不需要额外判断。我面试过不少候选人这道题能一次写对的人真的不多。最常见的错误是快指针多走了一步或少走了一步最终删错了节点。我的建议是写完代码后手动模拟一遍链表长度5删除倒数第2个慢指针最后应该停在倒数第3个节点上。6.3 合并两个有序链表合并有序链表的思路和合并两个有序数组一样双指针比较当前节点值小的那个先接上去。实现时有递归和迭代两种主流写法。def merge_two_lists(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next注意最后一步其中一个链表已经走完了剩下的直接拼接即可。很多新手在这里写一个while循环把剩余链表遍历接上其实完全没必要直接cur.next l1 if l1 else l2一行搞定。6.4 寻找链表中点找中点最优雅的方案还是快慢指针快指针每次走两步慢指针每次走一步快指针走到末尾时慢指针正好在中点。def find_middle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow这个技巧用处极广。链表排序中的归并排序要找中点切分回文链表判断也要找中点再反转后半段。快慢指针是链表世界里最省事的“一把梭”。7. 链表性能到底怎么样7.1 时间复杂度全表对照用一张表把链表和数组的核心操作复杂度摆清楚。操作数组链表随机访问按下标O(1)O(n)头部插入O(n)O(1)头部删除O(n)O(1)尾部插入有尾指针O(1)O(1)尾部插入无尾指针O(1)O(n)中间插入已知位置O(n)O(1)按值查找O(n)O(n)很多人会被“链表插入快”这句话误导以为只要插入就一定快。实际上链表插入的O(1)是有前提的——你已经找到了插入位置的前驱节点。如果你只知道要插入的值还得先花O(n)去遍历查找。加上遍历成本后链表往往并不比数组快多少。另外工程上还有一个残酷事实由于现代CPU有缓存机制数组这种连续内存结构在遍历时可以利用预取机制实际速度远高于链表。链表节点分散在内存各处每一次跳转都可能触发缓存未命中。所以千万不要因为理论上链表插入是O(1)就到处用链表很多时候数组更实际。7.2 空间开销对比链表每个节点都有额外指针开销。单链表多一个next引用双向链表多两个引用。在Python里每个对象本身还有对象头开销所以一个存储整数的链表节点换算下来可能比数组中一个整数多占好几倍内存。这也是为什么在内存敏感场景比如嵌入式、游戏引擎中链表用得越来越少。很多高性能系统更倾向于用动态数组如Python的list、Java的ArrayList加上标记删除法来模拟链表的插入删除语义。7.3 什么时候该用链表在Python日常开发中说实话链表用得并不多。但这不代表它没用需要频繁在头部插入删除且不知道总量时比如维护一个固定大小的最近浏览记录实现LRU缓存时双向链表哈希表大文件处理时数据无法一次性加载进内存用链表维护稀疏数据面试考察数据结构和指针操作时其他大多数场景Python内置的list和collections.deque已经完全够用了不要为了用链表而用链表。8. Python实现链表时的那些坑8.1 别被Python的可变对象引用绕晕Python的变量本质上是引用这导致链表中很多“赋值”操作跟C/C里的“赋值”不太一样。看下面这个经典陷阱a ListNode(1) b a b.val 2 print(a.val) # 2因为b和a引用同一个对象修改b.val后a.val也变了。这不是bug是Python的设计使然。但在实现链表时如果你没意识到这一步很容易在写插入删除时无意间通过某个别名修改了链表内容。解决建议明确区分“修改引用”和“修改对象”。cur cur.next是修改引用移动到下一个节点cur.val new_val是修改对象改变节点的值。两者混用时要格外小心。8.2 遍历循环里的死循环问题链表遍历最恐怖的事情是什么死循环。造成死循环的原因通常是链表本身被改成了环状结构。最常见的产生场景插入时指针顺序写反。比如你把node.next cur.next和cur.next node写反就会让cur的next指向自己形成一个一圈就回不来的环。# 错误的写法 cur.next node node.next cur.next # 此时cur.next已经被改成nodenode指向自己这种bug非常隐蔽因为有时候链表短或者数据碰巧正确它可能还不会暴露。一旦链表长了程序就会卡死在那。排查方法也很原始给遍历加上计数器超过一定次数直接抛异常。count 0 while cur: count 1 if count 1000000: raise RuntimeError(Possible cycle detected) cur cur.next8.3 递归反转链表的深度限制Python默认递归深度限制是1000层左右。如果你的链表有几万个节点用递归反转会直接报RecursionError。解决办法有两种一是用迭代法替代递归二是在递归前用sys.setrecursionlimit()调大限制。但调大限制本质上是在透支C栈链表十万个节点时依然会爆栈。我的建议是面试里递归写法可以展示思路但生产环境一定用迭代。不要图那几行代码的优雅稳定压倒一切。8.4 内存泄漏的错觉很多从C/C转过来的开发者会习惯性地想“删除节点后要不要手动释放内存”。在Python里完全不需要节点失去引用后垃圾回收器会自动处理。但这不意味着你可以随便丢掉节点。比如你删除了链表某个节点但代码里还有一个别的地方引用了它这个节点的内存就不会被回收可能造成“逻辑泄漏”。在写复杂链表操作时注意看有没有残留的引用指向已经“删除”的节点。9. 从链表到高级数据结构的延伸9.1 哈希表双链表实现LRU缓存LRULeast Recently Used缓存淘汰策略在Redis、MySQL、浏览器、操作系统中应用极广。用“哈希表双向链表”实现LRU是面试中最高频的系统设计题之一。思路哈希表负责O(1)的查找双向链表负责O(1)的插入删除和移动。访问一个数据时如果命中就把对应节点移到链表头部如果未命中且缓存已满就删除链表尾部节点并移除哈希表对应项。class LRUCache: def __init__(self, capacity): self.capacity capacity self.cache {} self.head DoublyListNode() self.tail DoublyListNode() 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.next self.head.next node.prev self.head self.head.next.prev node self.head.next node def get(self, key): if key not in self.cache: return -1 node self.cache[key] self._remove(node) self._add_to_head(node) return node.val def put(self, key, val): if key in self.cache: node self.cache[key] node.val val self._remove(node) self._add_to_head(node) else: node DoublyListNode(val) self.cache[key] node self._add_to_head(node) if len(self.cache) self.capacity: old_node self.tail.prev self._remove(old_node) del self.cache[old_node.key]代码里head和tail是哨兵节点不存实际数据专门用来减少边界判断。当缓存满了要淘汰时直接操作tail.prev就是最久未使用的节点。写这个题时我最常踩的坑是_remove和_add_to_head里指针更新的顺序搞混或者忘记更新哈希表。每一步操作后都检查一遍哈希表和链表的同步性能省很多调试时间。9.2 跳表给链表装上“电梯”链表查找慢的根本原因是必须逐个遍历。跳表的思路是在原始链表上额外建几层索引每层索引节点数量减半查找时从最上层往下跳。举个通俗的例子一本书有1000页你要找第500页。没索引就得从第1页翻到500页有目录的话你先翻到“第5章”附近再翻到“第5章第3节”几下就到了。跳表就是这样一个多级目录。Redis的有序集合底层用的就是跳表。跳表代码实现比链表复杂不少但如果你能把链表理解透跳表的核心结构也不过就是“多层的链表”。9.3 链表与算法设计的组合思路纵观大部分链表算法题核心技巧就那么几个虚拟头节点简化头节点删除和插入快慢指针判环、找中点、找倒数第N个节点链表反转局部反转用于判断回文、区间反转解构重排题目要求重排链表时先拆成两半再交替拼接这几个技巧分别解决不同问题组合起来又能衍生出一大批题。想练扎实的话建议把这几个基础动作手写五遍以上写到自己能闭着眼都不出错刷任何链表题都会轻松很多。10. 写在最后链表到底该怎么学链表最核心的价值不是让你在实际业务里天天写它而是帮你建立“指针操作”和“内存结构”这两种思维方式。很多人在初学链表时觉得难不是因为代码难写而是因为大脑还不习惯“通过引用来组织数据”的方式。这种思维方式一旦建立后面学树、图、并查集都会丝滑很多。我个人建议的学习路径是这样的先手写一遍单链表的基本操作再手写双链表然后去刷反转链表、判环、合并两个有序链表、删除倒数第N个节点这四道经典题。每一道题都分别用迭代和递归两种方式实现一遍并手动模拟边界情况。这样一轮下来链表的绝大多数考点你都有数了。最后送大家一个小技巧任何链表操作写完后先别急着跑测试用笔在纸上把那几个节点的指针变化画一遍。这比调试器管用因为链表问题的本质是逻辑问题画图能让你直接看到逻辑断点在哪里。我在实际写代码时还有一个习惯所有链表核心函数都要求自己能背写出来不靠编译器提示。不是为了炫技而是因为链表操作太基础了如果这些都要现场想那面试和工程里更复杂的数据结构设计根本没法快速推进。 
长河君 · 2026/10/10 2:21:57 · 阅读 1.2k 链表完全指南：Python实现与面试高频算法
1. 链表怎么就“火”了这两年不管是面试造火箭还是业务拧螺丝链表永远是数据结构里绕不开的一道坎。链表这种东西背概念容易真要手写实现、分析性能、处理边界情况翻车的人一抓一大把。我身边不少朋友在准备面试时链表题刷了一遍又一遍可一到“请用Python实现一个双向链表并支持在指定位置插入”这种题还是会卡壳。先说清楚这篇文章要讲什么链表的核心概念、内存布局、Python代码实现单链表和双链表都写以及面试和工程里最常见的几个操作和坑点。适合这么几类人看正在准备算法面试的开发者、初学数据结构的学生、以及在业务里需要用Python做底层数据存储优化的工程师。我会尽可能把链表讲的接地气一点因为链表本身并不复杂复杂的是很多人一开始没理解它和数组的根本差异导致后面越学越糊。这篇文章会把那些“老师没讲透、文档没写清”的地方一次性说清楚。2. 链表的本质与内存模型2.1 数组和链表的分水岭在哪数组和链表最大的区别不是“谁快谁慢”而是它们在内存里的组织方式完全不同。数组是一块连续的内存空间就像一栋楼的房间号是连着的住103的隔壁一定是104。这种连续性带来的好处是通过下标访问任何一个元素CPU可以直接算出它的内存地址时间复杂度是O(1)。坏处也明显插入或删除一个元素后面的所有元素都要挪位置尤其是插入在头部时整个数组都得搬家。链表则完全不同。链表里的节点散落在内存各处每个节点除了存自己的数据还要额外存一个指针或者叫引用指向下一个节点的位置。就像寻宝游戏每个线索会告诉你下一个线索藏在哪里你只能一个接一个地找不能跳着找。这个差异决定了几乎所有后续行为的对错判断随机访问数组快、链表慢插入删除链表快只要你知道位置、数组慢。理解了这个分水岭后边一切分析都顺理成章。2.2 单链表的基本结构拆解单链表是最简单的链表形态。每个节点包含两部分数据域和指针域。数据域存实际数据指针域存下一个节点的地址。用Python的类来表示就是这个样子class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这段代码是整个链表世界的基石。val可以是任意Python对象next要么是None表示链表到末尾了要么是另一个ListNode。你可能会问Python里不是所有东西都是对象引用吗为什么不直接用列表还非得自己写节点类答案是Python内置的list其实是动态数组为了解决连续内存的问题Python解释器会在底层维护一个指针数组当你插入元素时依然会有元素搬移的开销。而链表用节点引用的方式彻底绕开了内存连续性要求。为了更形象一点可以想象一列火车火车头是链表头节点每节车厢是一个节点车厢之间的连接钩子就是指针域。你要找第5节车厢的人只能从火车头开始一节一节往后找没别的办法。这就是链表的遍历逻辑。2.3 带头节点和不带头节点的区别链表实现里有一个经常让人懵的细节头节点。有些实现里会单独留一个不存数据的头节点dummy head有些实现直接让头指针指向第一个实际数据节点。我用一张场景来解释两者区别不带头节点链表为空时头指针是None。插入第一个节点时要特殊处理因为head本身得指向新节点。带头节点链表为空时头指针指向一个“空壳”节点这个节点的next是None。所有插入删除操作都可以统一处理不需要判断头指针为空的情况。在面试和工程代码里我强烈推荐用dummy head虚拟头节点它能省掉大量边界条件的判断。尤其是做链表删除类操作时虚拟头节点几乎能帮你避开所有“头节点被删了咋办”的崩溃瞬间。3. Python实现单链表从零到能写能改3.1 定义节点类和链表类刚刚已经定义了ListNode现在我们把整个单链表类写出来。这个类至少得支持以下操作获取长度、判断是否为空、遍历打印、尾部添加、头部添加、指定位置插入、删除指定位置、按值查找、按索引取值。class SingleLinkedList: def __init__(self): self.head None self.size 0 def is_empty(self): return self.size 0 def length(self): return self.size def travel(self): cur self.head result [] while cur: result.append(str(cur.val)) cur cur.next return - .join(result) if result else None (empty list) def add_first(self, val): node ListNode(val) node.next self.head self.head node self.size 1 def add_last(self, val): node ListNode(val) if self.is_empty(): self.head node else: cur self.head while cur.next: cur cur.next cur.next node self.size 1 def insert(self, index, val): if index 0 or index self.size: raise IndexError(Index out of range) if index 0: self.add_first(val) return if index self.size: self.add_last(val) return node ListNode(val) cur self.head for _ in range(index - 1): cur cur.next node.next cur.next cur.next node self.size 1这几个方法写完后单链表的基本骨架就出来了。注意insert方法里的边界判断——index可以等于size表示在末尾追加index必须是非负的index为0时直接头插。3.2 遍历链表的日常操作链表的所有操作几乎都建立在遍历之上。遍历的核心逻辑就一个while循环从头节点开始只要当前节点不是None就处理数据然后让指针后移。def travel(self): cur self.head while cur: print(cur.val, end - ) cur cur.next print(None)这里要提醒新手一个容易踩的坑很多人在遍历时会不经意间修改了原来的头节点。比如有人会写cur self.head然后遍历过程中又去改cur.next甚至直接self.head self.head.next这样链表结构就被破坏了。正确做法是永远用一个临时变量cur去操作不要动self.head本身除非你确实是在做头节点删除或插入。另外遍历的退出条件一定是cur is None不是cur.next is None。很多bug来源于此。如果条件是while cur.next:那么当cur指向最后一个节点时循环会继续但此时cur.next是None循环体里再访问cur.next.next直接报错。3.3 插入操作真正理解指针怎么玩链表的插入核心操作就两行之间的顺序问题node.next cur.next cur.next node这两行的顺序不能颠倒。如果先执行cur.next node那么原来的cur.next节点就找不到了链表从这里断掉后续所有节点全部丢失。通俗点说假如你站在一个队列中间要让新来的插到你后面你得先让新来的人拉住原来你身后那个人的手再让你自己拉住新来的人。如果你先松手去拉新人原来身后的人就没人理了。我在实际教学和面试辅导中发现至少一半的人第一次写插入时都会把这两行顺序写反。这个坑一旦掉进去链表就碎成了两段。还有一点需要注意在指定位置插入时我们要找的是目标位置的前一个节点。比如要在索引2的位置插入我们需要遍历到索引1的节点然后让新节点插入它后面。很多新手会遍历到索引2结果新节点插到了索引2的后面位置偏了一位。3.4 删除操作跳过那个节点就完事了吗删除的核心逻辑更简单只有一行cur.next cur.next.next就是让前一个节点直接指向被删节点的下一个节点所谓“跳过”。Python有垃圾回收机制被跳过的节点没有引用后会被自动回收不需要像C/C那样手动free。但删除有个非常容易被忽略的坑如果要删除的是头节点self.head self.head.next就可以了这个属于特殊情况。如果链表只有一个节点删除后head变成Nonesize归零。如果你用dummy head写法这些特殊情况会少很多。删除后别忘了size减一。很多人在写插入时记得加size写删除时却忘了减。这看起来是小问题但如果你后续实现了length()方法并利用它做循环判断size不准会导致各种离奇bug——比如循环多跑一次、索引判断失效。3.5 完整可运行的单链表代码把前面几段合并再补上查找和删除指定值的代码一个能直接跑的单链表类就完整了。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class SingleLinkedList: def __init__(self): self.head None self.size 0 def is_empty(self): return self.size 0 def length(self): return self.size def add_first(self, val): node ListNode(val) node.next self.head self.head node self.size 1 def add_last(self, val): node ListNode(val) if self.is_empty(): self.head node else: cur self.head while cur.next: cur cur.next cur.next node self.size 1 def insert(self, index, val): if index 0 or index self.size: raise IndexError(Index out of range) if index 0: self.add_first(val) return if index self.size: self.add_last(val) return node ListNode(val) cur self.head for _ in range(index - 1): cur cur.next node.next cur.next cur.next node self.size 1 def delete_by_value(self, val): cur self.head prev None while cur: if cur.val val: if prev is None: self.head cur.next else: prev.next cur.next self.size - 1 return True prev cur cur cur.next return False def find(self, val): cur self.head index 0 while cur: if cur.val val: return index cur cur.next index 1 return -1 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.val def travel(self): cur self.head result [] while cur: result.append(str(cur.val)) cur cur.next return - .join(result) if result else None (empty list) if __name__ __main__: sll SingleLinkedList() sll.add_last(10) sll.add_last(20) sll.add_first(5) sll.insert(2, 15) print(sll.travel()) # 5 - 10 - 15 - 20 print(sll.find(15)) # 2 sll.delete_by_value(10) print(sll.travel()) # 5 - 15 - 20这段代码建议直接跑一遍观察输出再手动改几个用例测试边界条件。比如不断往空链表里添加删除、在头部反复插入、删除头节点、删除尾部节点等。边界条件是链表最容易出错的地方多跑多试才有效果。4. 双向链表回头也能走凭什么4.1 为什么需要prev指针单链表只能从头往尾走这带来一个非常尴尬的问题你要删除某个节点必须知道它的前驱节点是谁。如果只给定一个当前节点单链表是没法直接删除它的——你找不到它前面是谁。双向链表就是来解决这个问题的。每个节点多了一个prev指针指向它的前一个节点。这样无论从前往后还是从后往前都能遍历。代价也很明确每个节点多存一个引用内存开销上升每次插入或删除需要多维护一个prev指针代码复杂度明显上升。4.2 双向链表节点定义与完整实现class DoublyListNode: def __init__(self, val0, prevNone, nextNone): self.val val self.prev prev self.next next class DoublyLinkedList: def __init__(self): self.head None self.tail None self.size 0 def is_empty(self): return self.size 0 def length(self): return self.size def add_first(self, val): node DoublyListNode(val) if self.is_empty(): self.head node self.tail node else: node.next self.head self.head.prev node self.head node self.size 1 def add_last(self, val): node DoublyListNode(val) if self.is_empty(): self.head node self.tail node else: node.prev self.tail self.tail.next node self.tail node self.size 1 def insert(self, index, val): if index 0 or index self.size: raise IndexError(Index out of range) if index 0: self.add_first(val) return if index self.size: self.add_last(val) return node DoublyListNode(val) cur self.head for _ in range(index): cur cur.next # 在 cur 之前插入 node node.prev cur.prev node.next cur cur.prev.next node cur.prev node self.size 1 def delete_by_value(self, val): cur self.head while cur: if cur.val val: if cur.prev: cur.prev.next cur.next else: self.head cur.next if cur.next: cur.next.prev cur.prev else: self.tail cur.prev self.size - 1 return True cur cur.next return False def travel_from_head(self): cur self.head result [] while cur: result.append(str(cur.val)) cur cur.next return - .join(result) if result else None (empty list) def travel_from_tail(self): cur self.tail result [] while cur: result.append(str(cur.val)) cur cur.prev return - .join(result) if result else None (empty list)这段代码里有两个细节值得好好琢磨。第一个是insert方法里找节点的策略。我选择遍历到index位置的节点cur然后把它前面插入新节点。这样做的好处是统一处理不管插入位置在哪逻辑都一样。但前提是你必须同时维护cur.prev的指向这个四步操作改node.prev、node.next、前节点的next、cur的prev顺序不能乱。第二个是delete操作里的“双向断开”。删除一个节点时要让前一个节点的next指向后一个节点同时让后一个节点的prev指向前一个节点。漏掉任何一个都会导致双向链表的指针结构断裂。4.3 删除时最容易被忽略的双向细节我在给同事Review代码时最常看到的问题就是双向链表删除时忘了更新tail或者忘了更新某个节点的prev。尤其当删除的是中间节点时很多人的第一反应是只做prev.next cur.next完全忘了cur.next.prev cur.prev这一句。我自己的习惯是删除逻辑写完后立刻做一轮遍历检查——从head走到tail再从tail走回head确认两次遍历的结果完全一致。这个习惯帮我发现过无数次低级但致命的指针错误。双向链表的好处不仅仅是能倒着走在面试题里LRU缓存淘汰算法、浏览器的前进后退功能底层都是它在支撑。后面我会专门讲这些应用场景。5. 循环链表封口之后玩法全变了5.1 循环链表的基本概念循环链表就是把单向链表最后一个节点的next从None改成指向head形成一个环。如果要双向循环那就是tail的next指向headhead的prev指向tail。最大特点任何一个节点都能作为起点遍历完整条链表。你从任意节点出发最终都能绕回自己。但这也带来一个麻烦遍历的终止条件不再是cur is None而是“我什么时候绕回起点了”。如果循环条件判断错了基本就是个死循环程序直接卡死。5.2 用快慢指针判断链表是否有环循环链表最经典的实战场景是“判断链表是否有环”。面试里考的最多的就是快慢指针法。原理非常简单两个指针同时从head出发快指针每次走两步慢指针每次走一步。如果链表有环快指针最终会追上慢指针两个指针在环内相遇如果没有环快指针会先走到None循环自然结束。def has_cycle(head): if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False为什么要快指针走两步而不是三步四步两步是最小安全步长能保证如果存在环快指针一定能在有限步内追上慢指针不会出现跨过去的情况。三步四步虽然也能判环但可能跳过慢指针导致永远相遇不了。我之前帮一个朋友调试过一个诡异问题链表检测时快指针走了三步结果链表明明有环却返回False。排查了半天发现就是步长问题。快慢指针判环步长选2是标准答案别乱改。5.3 找到环的入口节点判环只是第一步面试进阶题通常会追问如果链表有环请找到环的入口节点。这里有一个非常漂亮的数学结论快慢指针第一次相遇后把快指针重新放回head然后快慢指针都改为每次走一步两者再次相遇的位置就是环的入口。def detect_cycle_start(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None fast head while fast is not slow: fast fast.next slow slow.next return fast这个结论的推导过程不复杂假设head到环入口距离是a环入口到第一次相遇点距离是b环一圈长度是c。快指针走的路程是慢指针的两倍相遇时快指针比慢指针多走了n圈。设慢指针走了a b快指针走了a b n*c又因为快指针速度是两倍所以a b n*c 2(a b)化简得到a n*c - b这就意味着从head走到环入口的距离a完全等于从相遇点继续走到环入口的距离。所以把快指针重置到head两指针同速前进再相遇时必然是入口。这公式我每次写都要重新推一遍但推完再用代码实现基本不会错。6. 面试和工程里高频出现的链表场景6.1 反转链表迭代与递归两种姿势反转链表是链表题里的超级经典不会写基本等于没学过链表。迭代法思路用三个指针pre前一个节点、cur当前节点、next_temp存下一个节点边走边把当前节点的next改成指向pre。def reverse_list(head): prev None cur head while cur: next_temp cur.next cur.next prev prev cur cur next_temp return prev递归法的思路则是先走到最后一个节点然后逐层返回时修改指针方向def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head有人说递归很难懂但我个人觉得递归反转链表一旦理解后就再也忘不掉了。关键在于理解head.next.next head这行它让当前节点的下一个节点反过来指向自己完成局部反转。递归的返回值是反转后链表的头也就是原本链表的尾节点。6.2 删除倒数第N个节点这个题的标准解法是双指针快指针先走n步然后快慢指针一起走当快指针到达末尾时慢指针正好指向倒数第n个节点。def remove_nth_from_end(head, n): dummy ListNode(0, head) fast dummy slow dummy for _ in range(n): fast fast.next while fast.next: fast fast.next slow slow.next slow.next slow.next.next return dummy.next这里用dummy head的好处再次体现如果要删除的是真正的第一个节点慢指针在dummy节点上也能正常执行slow.next slow.next.next不需要额外判断。我面试过不少候选人这道题能一次写对的人真的不多。最常见的错误是快指针多走了一步或少走了一步最终删错了节点。我的建议是写完代码后手动模拟一遍链表长度5删除倒数第2个慢指针最后应该停在倒数第3个节点上。6.3 合并两个有序链表合并有序链表的思路和合并两个有序数组一样双指针比较当前节点值小的那个先接上去。实现时有递归和迭代两种主流写法。def merge_two_lists(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next注意最后一步其中一个链表已经走完了剩下的直接拼接即可。很多新手在这里写一个while循环把剩余链表遍历接上其实完全没必要直接cur.next l1 if l1 else l2一行搞定。6.4 寻找链表中点找中点最优雅的方案还是快慢指针快指针每次走两步慢指针每次走一步快指针走到末尾时慢指针正好在中点。def find_middle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow这个技巧用处极广。链表排序中的归并排序要找中点切分回文链表判断也要找中点再反转后半段。快慢指针是链表世界里最省事的“一把梭”。7. 链表性能到底怎么样7.1 时间复杂度全表对照用一张表把链表和数组的核心操作复杂度摆清楚。操作数组链表随机访问按下标O(1)O(n)头部插入O(n)O(1)头部删除O(n)O(1)尾部插入有尾指针O(1)O(1)尾部插入无尾指针O(1)O(n)中间插入已知位置O(n)O(1)按值查找O(n)O(n)很多人会被“链表插入快”这句话误导以为只要插入就一定快。实际上链表插入的O(1)是有前提的——你已经找到了插入位置的前驱节点。如果你只知道要插入的值还得先花O(n)去遍历查找。加上遍历成本后链表往往并不比数组快多少。另外工程上还有一个残酷事实由于现代CPU有缓存机制数组这种连续内存结构在遍历时可以利用预取机制实际速度远高于链表。链表节点分散在内存各处每一次跳转都可能触发缓存未命中。所以千万不要因为理论上链表插入是O(1)就到处用链表很多时候数组更实际。7.2 空间开销对比链表每个节点都有额外指针开销。单链表多一个next引用双向链表多两个引用。在Python里每个对象本身还有对象头开销所以一个存储整数的链表节点换算下来可能比数组中一个整数多占好几倍内存。这也是为什么在内存敏感场景比如嵌入式、游戏引擎中链表用得越来越少。很多高性能系统更倾向于用动态数组如Python的list、Java的ArrayList加上标记删除法来模拟链表的插入删除语义。7.3 什么时候该用链表在Python日常开发中说实话链表用得并不多。但这不代表它没用需要频繁在头部插入删除且不知道总量时比如维护一个固定大小的最近浏览记录实现LRU缓存时双向链表哈希表大文件处理时数据无法一次性加载进内存用链表维护稀疏数据面试考察数据结构和指针操作时其他大多数场景Python内置的list和collections.deque已经完全够用了不要为了用链表而用链表。8. Python实现链表时的那些坑8.1 别被Python的可变对象引用绕晕Python的变量本质上是引用这导致链表中很多“赋值”操作跟C/C里的“赋值”不太一样。看下面这个经典陷阱a ListNode(1) b a b.val 2 print(a.val) # 2因为b和a引用同一个对象修改b.val后a.val也变了。这不是bug是Python的设计使然。但在实现链表时如果你没意识到这一步很容易在写插入删除时无意间通过某个别名修改了链表内容。解决建议明确区分“修改引用”和“修改对象”。cur cur.next是修改引用移动到下一个节点cur.val new_val是修改对象改变节点的值。两者混用时要格外小心。8.2 遍历循环里的死循环问题链表遍历最恐怖的事情是什么死循环。造成死循环的原因通常是链表本身被改成了环状结构。最常见的产生场景插入时指针顺序写反。比如你把node.next cur.next和cur.next node写反就会让cur的next指向自己形成一个一圈就回不来的环。# 错误的写法 cur.next node node.next cur.next # 此时cur.next已经被改成nodenode指向自己这种bug非常隐蔽因为有时候链表短或者数据碰巧正确它可能还不会暴露。一旦链表长了程序就会卡死在那。排查方法也很原始给遍历加上计数器超过一定次数直接抛异常。count 0 while cur: count 1 if count 1000000: raise RuntimeError(Possible cycle detected) cur cur.next8.3 递归反转链表的深度限制Python默认递归深度限制是1000层左右。如果你的链表有几万个节点用递归反转会直接报RecursionError。解决办法有两种一是用迭代法替代递归二是在递归前用sys.setrecursionlimit()调大限制。但调大限制本质上是在透支C栈链表十万个节点时依然会爆栈。我的建议是面试里递归写法可以展示思路但生产环境一定用迭代。不要图那几行代码的优雅稳定压倒一切。8.4 内存泄漏的错觉很多从C/C转过来的开发者会习惯性地想“删除节点后要不要手动释放内存”。在Python里完全不需要节点失去引用后垃圾回收器会自动处理。但这不意味着你可以随便丢掉节点。比如你删除了链表某个节点但代码里还有一个别的地方引用了它这个节点的内存就不会被回收可能造成“逻辑泄漏”。在写复杂链表操作时注意看有没有残留的引用指向已经“删除”的节点。9. 从链表到高级数据结构的延伸9.1 哈希表双链表实现LRU缓存LRULeast Recently Used缓存淘汰策略在Redis、MySQL、浏览器、操作系统中应用极广。用“哈希表双向链表”实现LRU是面试中最高频的系统设计题之一。思路哈希表负责O(1)的查找双向链表负责O(1)的插入删除和移动。访问一个数据时如果命中就把对应节点移到链表头部如果未命中且缓存已满就删除链表尾部节点并移除哈希表对应项。class LRUCache: def __init__(self, capacity): self.capacity capacity self.cache {} self.head DoublyListNode() self.tail DoublyListNode() 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.next self.head.next node.prev self.head self.head.next.prev node self.head.next node def get(self, key): if key not in self.cache: return -1 node self.cache[key] self._remove(node) self._add_to_head(node) return node.val def put(self, key, val): if key in self.cache: node self.cache[key] node.val val self._remove(node) self._add_to_head(node) else: node DoublyListNode(val) self.cache[key] node self._add_to_head(node) if len(self.cache) self.capacity: old_node self.tail.prev self._remove(old_node) del self.cache[old_node.key]代码里head和tail是哨兵节点不存实际数据专门用来减少边界判断。当缓存满了要淘汰时直接操作tail.prev就是最久未使用的节点。写这个题时我最常踩的坑是_remove和_add_to_head里指针更新的顺序搞混或者忘记更新哈希表。每一步操作后都检查一遍哈希表和链表的同步性能省很多调试时间。9.2 跳表给链表装上“电梯”链表查找慢的根本原因是必须逐个遍历。跳表的思路是在原始链表上额外建几层索引每层索引节点数量减半查找时从最上层往下跳。举个通俗的例子一本书有1000页你要找第500页。没索引就得从第1页翻到500页有目录的话你先翻到“第5章”附近再翻到“第5章第3节”几下就到了。跳表就是这样一个多级目录。Redis的有序集合底层用的就是跳表。跳表代码实现比链表复杂不少但如果你能把链表理解透跳表的核心结构也不过就是“多层的链表”。9.3 链表与算法设计的组合思路纵观大部分链表算法题核心技巧就那么几个虚拟头节点简化头节点删除和插入快慢指针判环、找中点、找倒数第N个节点链表反转局部反转用于判断回文、区间反转解构重排题目要求重排链表时先拆成两半再交替拼接这几个技巧分别解决不同问题组合起来又能衍生出一大批题。想练扎实的话建议把这几个基础动作手写五遍以上写到自己能闭着眼都不出错刷任何链表题都会轻松很多。10. 写在最后链表到底该怎么学链表最核心的价值不是让你在实际业务里天天写它而是帮你建立“指针操作”和“内存结构”这两种思维方式。很多人在初学链表时觉得难不是因为代码难写而是因为大脑还不习惯“通过引用来组织数据”的方式。这种思维方式一旦建立后面学树、图、并查集都会丝滑很多。我个人建议的学习路径是这样的先手写一遍单链表的基本操作再手写双链表然后去刷反转链表、判环、合并两个有序链表、删除倒数第N个节点这四道经典题。每一道题都分别用迭代和递归两种方式实现一遍并手动模拟边界情况。这样一轮下来链表的绝大多数考点你都有数了。最后送大家一个小技巧任何链表操作写完后先别急着跑测试用笔在纸上把那几个节点的指针变化画一遍。这比调试器管用因为链表问题的本质是逻辑问题画图能让你直接看到逻辑断点在哪里。我在实际写代码时还有一个习惯所有链表核心函数都要求自己能背写出来不靠编译器提示。不是为了炫技而是因为链表操作太基础了如果这些都要现场想那面试和工程里更复杂的数据结构设计根本没法快速推进。