1. Top100链表题的整体盘子看起来简单翻车率却是第一梯队刷Top100的时候很多人对链表题抱一种心态题目看懂了代码也短应该是最不需要纠结的一类。真实情况恰恰相反。链表题在Hot 100里占比不算高但它绝对是提交失败率最高的题型之一。我复盘了自己和周围人的刷题记录发现共同问题不是不懂思路而是总拿数组的经验去理解链表写出来的Python代码在引用级别上完全不是自己以为的那个意思。先说清楚一点LeetCode上说的链表默认是单链表每个节点是一个ListNode对象。Python里不给裸指针但node.next other这句代码就是在改指针指向跟C语言里改node-next是同一个行为。唯一的差别是Python让你访问不到节点的地址只能通过对象引用操作这既是护身符也是迷魂汤——很多人写着写着就不知道自己手里的node到底指向哪个节点了。我先把Top100里的链表题盘一遍免得大家遗漏。下面这份清单基本覆盖了Hot 100官方列表里和链表强相关的题有的版本会把LRU缓存等归到设计类但底层拼的还是链表。题目难度核心套路206. 反转链表简单三指针原地反转92. 反转链表 II中等区间反转 虚拟头节点25. K 个一组翻转链表困难区间反转 分组处理24. 两两交换链表中的节点中等递归或穿针引线143. 重排链表中等找中点 反转 拼接141. 环形链表简单快慢指针142. 环形链表 II中等快慢指针 数学推导160. 相交链表简单双指针路径互换19. 删除链表的倒数第 N 个结点中等间隔双指针 虚拟头节点148. 排序链表中等快慢指针 归并排序21. 合并两个有序链表简单递归 / 迭代23. 合并 K 个升序链表困难分治 / 堆234. 回文链表简单后半段反转2. 两数相加中等模拟进位 哨兵节点146. LRU 缓存中等哈希表 双向链表把这15道题排一起看你马上会发现一个现象Top100把链表题能考的壳子基本都罩住了但内核就四套打法——反转、双指针、递归分治、穿针引线。后面我就按这四套打法逐题拆每道题给出可直接用的Python答案再讲讲代码里那些不写注释你复盘时根本想不起来的坑。动手刷之前先把通用节点结构写顺手。LeetCode已经内置了ListNode本地练题时也要自己定义一份方便调试class ListNode: def __init__(self, val0, nextNone): self.val val self.next next记住这个小东西后面所有代码都基于它。2. 反转与穿针引线链表题最霸道的两把刷子反转链表是整个链表章节的九九乘法表。你会发现K个一组翻转、重排链表、两两交换、回文链表最后都把问题归结到怎么把一段链表反转并且还能接回去。所以第一关必须把反转写到不带脑子也能正确的程度。2.1 206 反转链表先练成三指针本能最标准的解法是迭代三指针代码短到让人怀疑人生class Solution: def reverseList(self, head): pre, cur None, head while cur: nxt cur.next cur.next pre pre, cur cur, nxt return pre很多人第一次看这段代码觉得就这然后自己写就错。错的原因集中在两个地方。第一个地方是不理解为什么必须先存nxt。单链表只有一条next链你执行cur.next pre的那一刻cur后面那段链表就断了。如果不先拿nxt存一下循环下一步的cur nxt就取不到原来的下一个节点。我说句不太好听的这道题你就算逻辑全懂只要漏了nxt缓存那行提交也是必错。这个细节不是LeetCode独有的任何单链表原地修改都会遇到养成习惯比背代码重要。第二个地方是不理解为什么pre初始是None。因为反转之后原来的头节点变成了尾节点它的next必须指向None否则链表就没法正常结束。pre初始为None第一次循环里head.next None就顺带完成了这件事。2.2 25 K 个一组翻转链表区间反转是反转题的完全体206的进阶款就是K个一组翻转。这道题在Top100里属于困难但拆开看一眼其实就是三个子问题数够K个节点、反转这个K节点区间、把反转后的区间接回原链表。我直接给可运行的答案再解释核心逻辑class Solution: def reverseKGroup(self, head, k): dummy ListNode(0, head) prev dummy while True: # 尝试从头前驱向后走k步看够不够一组 tail prev for _ in range(k): tail tail.next if not tail: return dummy.next # 记录区间头和区间后第一个节点 start prev.next nxt_start tail.next # 局部反转 [start, tail] pre, cur nxt_start, start while cur is not nxt_start: nxt cur.next cur.next pre pre, cur cur, nxt # 接回原链表 prev.next tail prev start这段代码的精髓是prev这个指针。它始终指向当前要处理区间的前一个节点第一轮它指向dummy这样就解决了头节点也要反转时无处接手的问题。中间那个反转循环用的是206同样的三指针法唯一区别是pre的初始值不是None而是nxt_start。为什么因为反转后的尾节点也就是原来的start需要指向区间外的下一个节点否则整个区间反转完尾巴就悬空了。我踩过一次很深的坑反转完以后先更新了prev start再执行prev.next tail。这顺序看着没问题但prev指向的是反转后的尾节点你去改它的next等于直接把整条链表串到别的地方去了。正确顺序必须先把prev.next指向新头tail再把prev挪到新尾start。顺序反了不是报错而是死循环运行超时才给你颜色看。2.3 143 重排链表拆两半、反后半、穿针重排链表要求把L0 - Ln - L1 - Ln-1 - L2 - Ln-2 - ...这样交错排列。最直观的做法是拆三段走快慢指针找中点、反转后半段、然后交替拼接。代码我贴一份完整的class Solution: def reorderList(self, head): # 1. 快慢指针找中点 slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 2. 反转后半段并断开前后两段 cur slow.next slow.next None pre None while cur: nxt cur.next cur.next pre pre, cur cur, nxt second pre # 3. 前后交替拼接 first head while second: nxt1 first.next nxt2 second.next first.next second second.next nxt1 first nxt1 second nxt2这里有个新手特别容易忽略的点slow.next None必须做。如果不切断前半段的尾节点还指向后半段头节点链表就成了一个带环结构后面拼接时根本停不下来会一直绕圈。交错拼接的循环条件用while second而不是while first是因为反转后的后半段长度要么等于前半段偶数节点要么比前半段短一个奇数节点。每一轮把second的头节点插到first后面之后first要移动两步second移动一步最后一定是second先走完。假如用first做循环条件奇数个节点的场景会多出一次空指针操作直接AttributeError。2.4 24 两两交换递归是这里最不容易写错的写法两两交换有两种主流解法迭代的穿针引线麻烦且容易漏我推荐用递归。递归只需要想清楚一件事当前这一层我只负责交换前两个节点后面已经排好的链表递归函数会返回给我。class Solution: def swapPairs(self, head): if not head or not head.next: return head new_head head.next head.next self.swapPairs(new_head.next) new_head.next head return new_head拆解一下new_head是第二个节点head.next要接上递归处理完的后面一串new_head.next指回head完成两个节点的交换最后返回new_head因为它才是这一小段的新头。递归返回的是处理好的新一段的头所以每一层都能正确接上。这种写法的好处是压根不用维护一堆指针把边界条件交给递归出口处理。代价是递归栈深度等于链表长度的一半但Top100的测试数据远达不到爆栈级别用递归完全没问题。3. 双指针的三种高频考法环、相交、删倒数第N双指针在链表题里出现的频率高到让人麻木。Top100里跟双指针相关的链表题去掉重复套路真正值得反复消化的就三种快慢指针判环、双指针找相交点、间隔指针删倒数节点。掌握这三种排序链表找中点那类问题也顺手解决了。3.1 141 和 142快慢指针判环以及那个入口公式先看判断有没有环的141。思路是龟兔赛跑慢指针一次走一步快指针一次走两步如果链表有环快指针早晚会从后面追上慢指针如果没环快指针先到终点。class Solution: def hasCycle(self, head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False注意这里用的是is fast不是。链表节点是否存在环本质是判断两个指针是否引用同一个对象is才是Python里正确的对象身份比较。你写成在绝大多数测试用例里也能过因为ListNode没重载__eq__默认退化成is但语义上不严谨。142在141基础上多问一句环入口在哪这个问题的推导我很喜欢因为它不是玄学是可以一步步算出来的。设头节点到环入口的距离是a环入口到两指针相遇点的距离是b相遇点继续走到环入口的距离是c环一周长度就是bc。两指针相遇时慢指针走了ab快指针走了abn(bc)。快指针速度是慢指针两倍所以有2(ab) abn(bc) ab n(bc) a n(bc) - b当n1时a c。更通用的写法是a (n-1)(bc) c。这个式子的含义是相遇之后让一个指针从头节点开始走慢指针继续从相遇点走两者每次都走一步最后一定会在环入口相遇。代码实现class Solution: def detectCycle(self, head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: p head while p is not slow: p p.next slow slow.next return p return None相遇后那段代码里p从头走slow从相遇点走两者同步前进第一次相遇的位置就是入口。这个结论不用背现场推导一遍就记住了。3.2 160 相交链表走到尽头见你我就遇见了相交链表这道题的常规解法是哈希表先遍历A把节点对象存进set再遍历B找第一个命中。空间复杂度O(n)能过但不漂亮。面试官大概率会追问一句能不能O(1)空间这时候双指针才是正解。class Solution: def getIntersectionNode(self, headA, headB): p, q headA, headB while p is not q: p p.next if p else headB q q.next if q else headA return p原理很巧妙两个指针分别从A和B头节点出发每走一步如果走到None就换到另一条链的头部继续走。因为两条链的总长度固定是lenA lenB等两个指针都走过各自整条链并互换一次之后它们走过的路程完全一样此时如果有交点它们必然在第一个交点相遇如果没有交点它们会同时走到None循环终止于p is q返回None。这个写法的判断条件是p is not q而不是p and q。因为当两个指针都走到None时p is q成立循环应该结束如果写成while p ! q或者while p and q无交点的场景要么进入死循环要么提前返回错误结果。我最初就是用while p ! q在某个无交点的大数据用例上超时了一回后来才发现!在Python里会走ListNode.__ne__逻辑上也处理不了两个None相等的情况。3.3 19 删除倒数第N个间隔双指针配上dummy才稳妥删除链表的倒数第N个节点核心思想是让两个指针之间隔出N步然后一起往后走前面的指针走到链表末尾时后面的指针正好停在倒数第N个节点的前一个位置。关键是前一个位置因为删节点的本质是prev.next prev.next.next你必须拿到待删节点的前驱。class Solution: def removeNthFromEnd(self, head, n): dummy ListNode(0, head) fast slow dummy for _ in range(n 1): fast fast.next while fast: fast fast.next slow slow.next slow.next slow.next.next return dummy.next为什么fast要先走n1步因为slow最后要停在待删节点前面两者间隔应该是n1个节点。举例说删除倒数第1个节点时slow应该指到倒数第2个节点fast走完整个链表后位于Noneslow刚好在正确位置。dummy在这里是必须的不是可有可无。如果链表只有一个节点而且删的就是它那么slow初始指向头节点不借助dummyslow.next slow.next.next会试图访问None.next直接崩溃。有了dummy头节点也变成中间节点不需要特殊分支。这种用一个假头节点消除边界判断的习惯在链表题里叫哨兵模式后面所有涉及删除头节点的题都适用。顺带把148排序链表的双指针用途也说了。排序链表要求O(nlogn)时间能在链表上稳定实现的最好选择是归并排序而归并排序第一步就是找中点。链表找中点没法随机访问只能用快慢指针class Solution: def sortList(self, head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None left self.sortList(head) right self.sortList(mid) return self.merge(left, right) def merge(self, 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这里fast初始化为head.next是有讲究的。如果fast head两个指针从头一起走偶数长度的链表最后slow会指到中间两个节点中偏后的那个导致分割后左半段比右半段多一个节点递归处理虽然不会错但分割不平衡会拖慢速度。初始化fast head.nextslow最终会停在偏左的中点两侧长度差控制在1以内归并效率更稳定。分割后slow.next None这步同样不能省上一题重排链表已经吃过这个亏了。链表归并有个天然好处合并两条有序链表时不需要额外数组靠改next指针就能完成这也是它能做到O(1)辅助空间不算递归栈的原因。4. 递归与归并帮你省掉一半重复代码的接骨术递归在链表题里的地位很多人低估了。链表本身就是递归定义出来的数据结构一个链表要么是空要么是一个节点后接一个小链表。这个定义意味着很多链表操作天然适合递归表达。Top100里至少四道题的最佳解都和递归有关。4.1 21 合并两个有序链表递归就是把接骨交给下一层合并两个有序链表迭代写法是用dummy 双指针大家可以自己练。递归写法的思路是每一次只比较两个头节点谁小谁做新链表的头谁剩下的部分继续交给递归处理。class Solution: def mergeTwoLists(self, l1, l2): if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next self.mergeTwoLists(l1.next, l2) return l1 else: l2.next self.mergeTwoLists(l1, l2.next) return l2这个写法最需要注意的地方是base casenot l1或not l2时直接返回另一个链表。这个出口不是随便写的它把其中一条链已经空了剩下整条链直接接上这个终止条件封装住了递归才能一层层往上回溯时拼出完整结果。递归的空间复杂度是O(min(lenA, lenB))因为每一层递归都要占用一个函数栈帧。迭代写法的空间是O(1)。单从性能讲迭代更优但递归代码的清晰度明显更高合并K个链表时会发现递归思想还能继续放大招。4.2 23 合并K个升序链表分治是递归的正确打开方式给你K个有序链表合并成一个有序链表。最单纯的思路是顺序合并拿第1和第2条合并结果再和第3条合并一直到最后。这个方案的总复杂度是O(kN)如果K很大前面合并出来的长链会被反复合并多次性能糟糕。真正推荐的是分治合并也可以理解成给K条链表做归并排序的合并阶段两两合并再把合并结果继续两两合并类似一棵二叉树。class Solution: def mergeKLists(self, lists): if not lists: return None def merge(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 def seg(lo, hi): if lo hi: return lists[lo] mid (lo hi) // 2 left seg(lo, mid) right seg(mid 1, hi) return merge(left, right) return seg(0, len(lists) - 1)递归每次把区间对半分复杂度从顺序合并的O(kN)降到O(Nlogk)。这里的N是所有链表节点总数k是链表条数。比如100条平均每条10个节点的链表顺序合并接近10000次节点比较分治只要约7000次K越大差距越明显。另外多说一句这道题也可以用堆来做把每条链表的头节点放进最小堆每次弹出最小的再把它的next压入堆。Python的heapq需要给ListNode定义__lt__比较方法否则堆内比较会报错这比分治代码多绕一层。面试时如果时间紧分治更容易写对而且空间上递归栈深度是O(logk)比堆的O(k)空间省太多。4.3 234 回文链表后半段反转法还是那个熟悉的味道判断链表是否回文。最简单粗暴的思路是把链表转成数组然后双指针从两端往中间比。空间O(n)代码不到十行但面试一定会被问能不能O(1)空间。O(1)空间的解法用到的仍然是三板斧快慢指针找中点、反转后半段、逐节点比较。只要前面2.1和3.4学扎实了这道题就是白送分。class Solution: def isPalindrome(self, head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next # 反转后半段 pre, cur None, slow while cur: nxt cur.next cur.next pre pre, cur cur, nxt second pre # 比较 first head while first and second: if first.val ! second.val: return False first first.next second second.next return True比较循环里用的是first.val ! second.val不是first is not second。回文判断关心的是节点值相等不是节点对象同一性这里如果写错就会所有用例全错。反转后半段不需要断开slow的next因为反转后整个后半段都脱离了原来的位置比较时只走second链不会碰到原来的后半段所以不会死循环。如果你有强迫症想比较完把链表恢复原状可以在反转时记录一下原来的尾节点再反转一次接回去。LeetCode不会检查链表是否被修改但真实面试里主动恢复会给面试官留下好印象。4.4 2 两数相加模拟进位注意最后别丢掉那个1两数相加的链表版本质是小学加法竖式。每个节点存一位数字链表头是个位两个链表相加要模拟从低位到高位的进位。class Solution: def addTwoNumbers(self, l1, l2): dummy ListNode(0) cur dummy carry 0 while l1 or l2 or carry: v1 l1.val if l1 else 0 v2 l2.val if l2 else 0 total v1 v2 carry carry total // 10 cur.next ListNode(total % 10) cur cur.next if l1: l1 l1.next if l2: l2 l2.next return dummy.next这个题最大的坑是循环结束条件。很多人写成while l1 or l2遇到一模一样的两条最长链表都没问题但是当l1 [5]、l2 [5]这种需要产生额外进位的输入第二步cur.next ListNode(1)就被跳过去结果返回[0]而不是[0, 1]。所以我循环条件里特意带了or carry让最后的进位也能生成新节点。另一个常见错误是在循环内部用if l1.next来移动指针。l1本身是节点对象判断它存不存在用if l1而不是if l1.next。如果当前节点是最后一个但值存在l1.next是None条件为假指针就卡住不动了。这种错误在本地测试时很难发现因为单测用例太少。5. Python链表题的五个高频翻车点和一套自测方法代码都贴完了最后把我在刷题和给同事做code review时见过最多的五个翻车点集中说一下。这些虽然不是题目答案但我觉得比任何一道题的答案都值钱。5.1 翻车点一把找下一个节点和修改下一个节点混为一谈看这个错误模式cur cur.next # 先移动 cur.next pre # 然后修改在206反转链表里这么写必错。因为cur cur.next已经让cur指向下一个节点了你再执行cur.next pre改的是下一个节点的next而不是当前节点的next整个反转逻辑全乱。正确顺序永远是先nxt cur.next缓存再改cur.next pre最后才移动cur nxt。记住一句话在修改一个节点的next之前如果你还需要它原来的next就必须先存下来。5.2 翻车点二拼接区间时顺序颠倒K个一组翻转那道题反转完区间要同时做两件事把前面节点的next指向新区间头把前驱指针移动到新区间尾。正确顺序是先prev.next tail再接prev start。如果反过来prev已经指向了start新区间的尾部再执行prev.next tail等于把tail接到start的后面链表瞬间打个大结。而且这种错不报异常只在提交时表现为超时或者结果乱序溯源特别费劲。5.3 翻车点三打印链表看到一屏幕地址Python默认没有给ListNode实现__repr__print一个节点出来是__main__.ListNode object at 0x...。链表越长输出越是一堆地址完全没法看。我习惯在本地定义结构时顺手加一个辅助转换函数def to_list(head): res [] while head: res.append(head.val) head head.next return res每次调试打印to_list(res)一眼就能看出结果对不对。刷题阶段不要嫌这个函数多余它能帮你省下大量肉眼模拟指针移动的时间。5.4 翻车点四忽略LeetCode输入和本地入参的差异LeetCode的链表题目在网页上显示输入是数组例如head [1,2,3,4]但你的函数签名接收的是ListNode对象。这意味着你在本地测试时需要自己把数组转成链表。忘了这步很多人在本地跑Solution().reverseList([1,2,3])发现head.next不存在直接怀疑人生的例子我见过太多了。写个build函数五分钟的事def build_linked_list(vals): dummy ListNode(0) cur dummy for v in vals: cur.next ListNode(v) cur cur.next return dummy.next自测时head build_linked_list([1, 2, 3, 4, 5]) res Solution().reverseList(head) print(to_list(res))这套组合拳在手所有Top100链表题都能在本地快速验证。5.5 翻车点五环没断开测试跑到超时环形链表入环、重排链表、排序链表这三道题都涉及把一条链断成两条。断链操作slow.next None经常被当成无关紧要的边界处理随手删掉。但链表一旦残留环任何遍历都不会停本地测试直接卡死LeetCode提交则显示Time Limit Exceeded。如果你遇到代码明明应该是对的但一跑就超时第一反应就是查有没有哪里漏了断链。关于自测我的习惯是每道题提交前至少跑三组数据空链表、单个节点、两个节点。这三组用例能覆盖掉80%的边界条件错误。链表题和数组题不一样数组题空数组通常直接给答案链表题空链表则要小心别在head.next上踩空。刷字符串和数组题时错误往往来自逻辑分支链表题的错误则几乎全是指针引用和边界。你在本地把to_list和build_linked_list这两个工具函数准备好每道题写完之后强制走一遍三组小用例Top100里链表这组通过率会明显比周围人高。最后再说一个我自己的固执习惯所有涉及修改链表结构的题写代码前先在草稿纸上把pre、cur、nxt三个指针在关键步骤的指向画出来画完再写代码。这个习惯帮我杜绝了至少一半的指针错位问题你可以试试。