企业官网建设流程全解析

1. Top100链表题的整体盘子：看起来简单，翻车率却是第一梯队

刷Top100的时候，很多人对链表题抱一种心态：题目看懂了，代码也短，应该是最不需要纠结的一类。真实情况恰恰相反。链表题在Hot 100里占比不算高，但它绝对是提交失败率最高的题型之一。我复盘了自己和周围人的刷题记录，发现共同问题不是不懂思路，而是总拿数组的经验去理解链表，写出来的Python代码在引用级别上完全不是自己以为的那个意思。

先说清楚一点：LeetCode上说的链表，默认是单链表，每个节点是一个ListNode对象。Python里不给裸指针，但node.next = other这句代码就是在改指针指向，跟C语言里改node->next是同一个行为。唯一的差别是，Python让你访问不到节点的地址，只能通过对象引用操作，这既是护身符也是迷魂汤——很多人写着写着，就不知道自己手里的node到底指向哪个节点了。

我先把Top100里的链表题盘一遍，免得大家遗漏。下面这份清单基本覆盖了Hot 100官方列表里和链表强相关的题，有的版本会把LRU缓存等归到设计类，但底层拼的还是链表。

把这15道题排一起看，你马上会发现一个现象：Top100把链表题能考的壳子基本都罩住了，但内核就四套打法——反转、双指针、递归分治、穿针引线。后面我就按这四套打法逐题拆，每道题给出可直接用的Python答案，再讲讲代码里那些不写注释你复盘时根本想不起来的坑。

动手刷之前，先把通用节点结构写顺手。LeetCode已经内置了ListNode，本地练题时也要自己定义一份，方便调试：

class ListNode: def __init__(self, val=0, next=None): 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，环一周长度就是b+c。两指针相遇时，慢指针走了a+b，快指针走了a+b+n(b+c)。快指针速度是慢指针两倍，所以有：

2(a+b) = a+b+n(b+c) a+b = n(b+c) a = n(b+c) - b

当n=1时，a = c。更通用的写法是a = (n-1)(b+c) + 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要先走n+1步？因为slow最后要停在待删节点前面，两者间隔应该是n+1个节点。举例说，删除倒数第1个节点时，slow应该指到倒数第2个节点，fast走完整个链表后位于None，slow刚好在正确位置。

dummy在这里是必须的，不是可有可无。如果链表只有一个节点，而且删的就是它，那么slow初始指向头节点，不借助dummy，slow.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.next，slow最终会停在偏左的中点，两侧长度差控制在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 case：not 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三个指针在关键步骤的指向画出来，画完再写代码。这个习惯帮我杜绝了至少一半的指针错位问题，你可以试试。