企业官网建设流程全解析

刷LeetCode Hot100的人大部分会先冲数组、哈希表、动态规划这些大板块，链表题往往被放到后面草草刷完。但我自己的感受恰恰相反：链表题是最该放在早期、也最不该丢分的一类。一来它的套路高度收敛，翻来覆去就是快慢指针、虚拟头节点、反转、合并这几招，二来它专门考察“指针操作 + 边界条件”两项硬功夫，而这正是面试手写代码时最容易翻车的地方。这篇内容围绕LeetCode Hot100中的链表题目，把高频题按题型拆开讲，给出能直接照抄的思路和代码，同时分享一些题解里不会明说的坑。适合准备算法面试、想把Hot100刷扎实、以及做完题总在边界条件上栽跟头的朋友。

1. 为什么Hot100的链表题是最不该丢分的一类题

1.1 链表考点在Hot100中的分布与出题规律

Hot100的链表章节题目大概有十来道，数量看着不多，但覆盖的题型非常集中。我粗看了一下，主要就是：反转链表、环形链表、相交链表、回文链表、删除倒数第N个节点、合并有序链表、两数相加、排序链表、K个一组翻转链表、LRU缓存。这些题单拎出来每一道都有变化，但往深处拆，本质全是“指针如何挪动”和“边界在哪”。

出题人为什么爱考链表？有一个很重要的原因：数组题可以用下标取巧，很多边界问题靠索引就能避免；链表没有下标，所有操作都是顺着引用走，一旦思路不清晰，写出来的代码就会出现空指针、死循环、断链这些问题。面试官考链表，表面考算法，实际在考你的代码基本功和“能不能在脑子里维护指针状态”。

所以我的建议是：把链表题当作独立专题集中刷，不要今天刷一道、明天隔十道才碰另一道。集中刷的好处是能快速识别题目间的共性，比如“合并两个有序链表”和“合并K个升序链表”是一脉相承，“反转链表”和“K个一组翻转链表”又是一个套路。刷到后面你会发现，新题基本是老方法的排列组合。

1.2 链表题的本质：指针操作能力与边界意识

链表题做得顺不顺，关键看两件事。

第一是断链前的保存意识。在Java里直接操作引用、在C++里操作指针，改next之前如果不先保存原来的后驱节点，改完之后剩下的后半段链表就找不回来了。Python虽然引用传递也算直观，但同样存在这个问题。很多链表题的常见错误，比如反转写崩、插入写乱，根源都是“改了next但没保存原来的next”。

第二是循环条件的边界。常见写法while cur和while cur.next完全是两种语义。用哪一种取决于你要不要处理最后一个节点，以及会不会在循环体里访问cur.next.next。LeetCode上被报空指针异常，一大半是循环条件选错了。

这两项能力没有捷径，只能靠画图和反复验证。你可以在脑子里画，最好在草稿纸上画。我刷链表题时有个习惯，每道题动手之前先把“空的链表”、“只有一个节点”、“只有两个节点”、“到达最后一个节点”这四种情况在脑子里过一遍，很多边界问题当场就暴露了。

1.3 两条主线方法论：虚拟头节点 + 快慢指针

如果把链表题梳理成一套心法，最核心的其实就两条：虚拟头节点和快慢指针。

虚拟头节点（dummy节点）解决的是“头节点可能被修改”的问题。删除头节点、在头节点前插入、反转整条链表这类操作都会让head本身发生变化，如果不做特殊处理，就要单独写if判断。而挂一个dummy节点，让它指向head，所有操作都统一在dummy的后续链上进行，最后返回dummy.next，代码会简洁非常多。Hot100链表题里，删除倒数第N个节点、删除排序链表中的重复元素、合并两个有序链表、K个一组翻转链表，全部可以靠dummy简化。

快慢指针解决的是“定位问题”。找链表中点、判断是否有环、找环的入口、找倒数第K个节点，本质上都是让一个指针走一步、另一个指针走两步，或者让一个指针先走K步再同步移动。这类题在Hot100里的占比相当高，甚至回文链表这种看似无关的题，正确解法也是“快慢指针找中点 + 反转后半段”。

掌握了这两条主线，再去逐题拆解，心里就有底多了。

2. 反转类题目：一道反转题吃透三种写法

2.1 206反转链表：迭代与递归两种模板

反转链表是整个链表题的核心，单考或者是其他题的前置步骤都特别常见。迭代写法最重要的就是“先保存后继”，在我之前的经验里，可能有八成初学者第一次写反转都死在没保存当前节点的下一个引用。

def reverseList(head): prev = None cur = head while cur: nxt = cur.next cur.next = prev prev = cur cur = nxt return prev

这个代码的每一步都很关键：nxt先保存cur后面的一整段；然后让cur的next指向prev；接着prev和cur同时向后走。循环结束后，cur是None，prev是新的头节点，正好返回prev。

递归写法在做题里也经常出现，思路是“把后面的链表先反转好，再让当前节点的后一个节点指向当前节点”。

def reverseList(head): if not head or not head.next: return head new_head = reverseList(head.next) head.next.next = head head.next = None return new_head

用递归有个细节：base case要同时判断head为空或head.next为空，否则只有一个节点时返回null就出问题。递归的好处是代码短，坏处是有O(n)的调用栈空间，如果链表特别长、或者面试官要求O(1)额外空间，还是用迭代更稳妥。我个人的偏好是刷题用迭代，因为在很多后续题目里，迭代反转可以当子函数直接复用，而递归往往不太好嵌套。

2.2 92反转链表II：局部反转先拆后合

反转链表II要求只反转left到right这一段，剩下保持原序。很多人的第一反应是“找到区间然后断开，反转完再接回去”，这个思路可行但容易乱。更稳的做法是头插法：在区间内遍历一遍，把每个新遇到的节点插到区间开头之前，期间不断开原链表的链接。

def reverseBetween(head, left, right): dummy = ListNode(0, head) pre = dummy for _ in range(left - 1): pre = pre.next cur = pre.next for _ in range(right - left): nxt = cur.next cur.next = nxt.next nxt.next = pre.next pre.next = nxt return dummy.next

这个头插法和反转整条链表的代码不一样，它不需要额外的prev变量，而是每次都把nxt摘出来放到pre后面。整个过程链表的其他部分，例如left之前的节点和right之后的节点，始终没有被破坏，所以最后完全不需要重新拼接。我建议读者把这段代码多默写几遍，它比“断开再拼接”的做法少踩很多坑。

2.3 25 K个一组翻转链表：分组反转的通用框架

这道题是反转类题目的进阶版，也是Hot100里链表题的综合压轴之一。它要求每K个节点一组反转，不足K个保持原样。

直接递归+迭代混用的方法比较容易理解：先数一下整条链表长度，确认有几组需要反转；然后每一组执行一次标准反转，把上一组的结尾接到新反转后的头部，再把本组的结尾接到下一组的头部。

这里给出一版基于哑节点的迭代解法：

def reverseKGroup(head, k): dummy = ListNode(0, head) pre = dummy while True: end = pre for _ in range(k): end = end.next if not end: return dummy.next start = pre.next nxt = end.next end.next = None pre.next = reverseList(start) start.next = nxt pre = start

关键点在于：每次反转前，先找到本组的end；然后把本组后面那一段的起始节点nxt保存下来；接着切断end的next，对本组做标准反转；反转完成后start变成了本组的尾节点，让它指向nxt，链表就接回去了。如果用递归写会短一些，但理解难度更高，我在这里就不展开了。

这道题最容易错的地方，是反转之后没有把本组的尾部接到下一组，或者上一组的尾部没有指向新反转组的头部。用dummy节点统一之后，“上一组是谁”这个问题被简化成了pre变量，逻辑清楚很多。

3. 快慢指针与环的判定：从入门题到进阶联动

3.1 141环形链表与142环形链表II：双指针的数学原理

环形链表这道题，最经典的解法就是快慢指针：快指针每次走两步，慢指针每次走一步，如果存在环，两者必然在某处相遇。相遇的原因是，进入环之后，快指针相对于慢指针每次追近1步，速度差恒为1，因此一定能追上。

判断“是否有环”只需要相遇条件；判断“环的入口”就多了一步。在第一次相遇之后，把慢指针移动回头节点，然后让快慢指针都以一步的速度往前走，再次相遇的位置就是环的入口。这个结论的推导很多题解都写过，我的理解是：从链表头到环入口的距离，恰好等于第一次相遇点顺着环走到入口的距离，所以两个指针同速前进，必然在入口处碰到。

def detectCycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: slow = head while slow != fast: slow = slow.next fast = fast.next return slow return None

这里特别提醒一下判断顺序：while fast and fast.next这两个条件都要挨个判断，不能只写fast，不然fast.next为None时再访问fast.next.next就会报空指针。我调试环形链表时踩过好几次这个坑，后来把判断条件默认写成这两条，才没再犯。

3.2 876链表的中间结点与234回文链表：快慢指针找中点

链表的中间结点这道题看着简单，但它是回文链表的前置步骤，而且暗含一个边界细节：当链表长度为偶数时，快慢指针的循环条件决定中间节点是哪一个。

def middleNode(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow

当链表有6个节点，slow会停在第四个节点，也就是“第二个中间节点”。回文链表恰好需要这个位置：找中点 -> 反转后半段 -> 从两头比较。如果不注意这个细节，用递归栈之类的先入后出也能做，但空间复杂度就不是O(1)了。

回文链表的完整实现可以这样写：

def isPalindrome(head): slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next second = reverseList(slow) first = head while second: if first.val != second.val: return False first = first.next second = second.next return True

这段代码里没有把链表恢复原状，因为判断完就结束了，不需要再恢复。但如果在实际工程里你还要继续用这条链表，记得反转后再反转回去。

3.3 19删除链表的倒数第N个结点：少走一遍的做法

删除倒数第N个节点，常规思路是“先走一遍数长度，再走一遍找位置”，但双指针可以一遍搞定。让快指针先往前走N步，然后快慢指针一起走，当快指针到链表尾的时候，慢指针正好停在待删除节点的前一个节点。

def removeNthFromEnd(head, n): dummy = ListNode(0, head) fast = 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

这里有一个容易搞混的细节：fast先走N步还是N+1步。如果fast从dummy先走N步，最后slow停在待删节点的前驱；如果fast从头节点先走N步，最后slow就正好停在待删除节点上。两种写法都能做，但你要知道自己写的是哪一种，避免后面的删除操作多走或少走一步。我习惯统一从dummy出发，fast先走N步，因为这样删除时用slow.next = slow.next.next逻辑最顺手。

4. 删除、去重与合并：边界条件最密集的区域

4.1 删除排序链表中的重复元素II：dummy节点统一边界

这道题是Hot100把“去重”考到极致的题目：排序链表中可能有连续出现的重复元素，要求把所有重复过的节点全部删掉，一个不留，比如1-2-3-3-4-4-5变成1-2-5。难点在于，头节点可能本身就是重复的，比如1-1-2，那要删的就是头节点。解决方式依然是dummy节点。

def deleteDuplicates(head): dummy = ListNode(0, head) pre = dummy cur = head while cur: if cur.next and cur.val == cur.next.val: while cur.next and cur.val == cur.next.val: cur = cur.next pre.next = cur.next else: pre = pre.next cur = cur.next return dummy.next

这题的思路是：一旦发现cur和cur.next值相同，就把cur一路移动到该重复段的最后一个节点，然后把pre的next直接指向cur.next，跳过整段重复；如果没遇到重复，pre跟着cur往后走。很多人在“pre到底要不要跟着走”这里犹豫，其实只要记住：只有确认当前段无重复时，pre才往后移动一位；只要发生了删除，pre就停留在当前位置，等待连接下一个不重复的节点。

4.2 21合并两个有序链表与23合并K个升序链表：从双指针到优先队列

合并两个有序链表是链表题里的“必修课”，循环体非常短，核心就一句话：谁小接谁。

def mergeTwoLists(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

循环结束后把剩余的整段链表直接接上，不需要再逐节点移动，这是链表和数组处理的一个显著区别：数组要逐个复制，链表引用直接指过去就行。

合并K个升序链表是它的进阶版本。最朴素的做法是两两合并，时间复杂度O(kN)；更好的做法是用一个大小为K的最小堆，每次从堆里取出最小值节点，然后把它后一个节点压入堆。

import heapq def mergeKLists(lists): dummy = ListNode(0) cur = dummy heap = [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) while heap: val, i, node = heapq.heappop(heap) cur.next = node cur = cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next

堆里存的元组带着三个元素：(节点值, 链表索引, 节点本身)。加一个索引很重要，因为Python的元组比较是按顺序来的，如果两个节点值相同，它会去比较第二个元素，而节点本身没实现比较运算，不写索引很可能报类型错误。这是Python刷这道题最容易踩的坑。

4.3 2两数相加：模拟加法进位时的空间处理

两数相加这道题其实是在链表上做竖式加法。链表的头节点代表数字的最低位，两个链表可能长度不同，而且最后可能多出一个进位，这些都是需要处理的地方。

def addTwoNumbers(l1, l2): dummy = ListNode(0) cur = dummy carry = 0 while l1 or l2 or carry: x = l1.val if l1 else 0 y = l2.val if l2 else 0 s = x + y + carry carry = s // 10 cur.next = ListNode(s % 10) cur = cur.next if l1: l1 = l1.next if l2: l2 = l2.next return dummy.next

循环条件写成l1 or l2 or carry是最省心的一种，它天然处理了“一条链表走完另一条还有剩余”和“最后还有一个进位”这两种情况。举一个容易漏的例子：9+9结果是18，循环结束后carry=1，如果不处理这一个进位，结果链表就只有8，缺少最高位的1。这道题虽然简单，但能很好检验你有没有养成“处理收尾状态”的习惯。

5. 排序、重排与设计题：链表题的天花板在这里

5.1 148排序链表：自底向上归并排序的工程价值

排序链表要求时间复杂度O(n log n)、空间复杂度O(1)。满足这个要求的做法只有归并排序，而且自底向上的归并排序才是严格意义上的O(1)空间。自顶向下的递归归并写法更直观，但递归栈会带来O(log n)空间，面试时如果面试官追问，需要能说清楚两者的差别。

自顶向下的思路大家应该都能理解：快慢指针找到中点，切成左右两半，分别排序，再合并。我把核心代码贴出来，重点看切分和合并两个子过程。

def sortList(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 = sortList(head) right = sortList(mid) return mergeTwoLists(left, right)

这条代码里有一个容易被忽略的细节：找中点时fast的初始值设置成了head.next，而不是head。原因是如果fast也从head开始，当链表只有两个节点时，slow会停在第二个节点上，分割后左半段就为空了。把fast初始化为head.next，正好能让偶数长度的链表在中点前均匀切开，这也是一个典型的“边界条件藏在初始化里”的例子。

5.2 143重排链表：找中点+反转+穿插合并

重排链表要求把L0 -> Ln -> L1 -> Ln-1 -> ...这个顺序重新连接起来。这题本质上是之前几个技巧的组合拳：先找中点，再把后半段反转，然后交错合并两条链表。

def reorderList(head): if not head or not head.next: return slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next second = reverseList(slow.next) slow.next = None first = head while second: tmp1 = first.next tmp2 = second.next first.next = second second.next = tmp1 first = tmp1 second = tmp2

这道题的合并部分和普通合并不一样，普通合并是“取小的”，这里是“交替取”，所以循环里要同时保存两条链表的下一跳，不然一旦修改next，后面的节点就找不到了。有些题解会把前后两半合并过程单独抽成一个函数，我建议你也这么做，将来遇到类似的“交替拼接”题目可以直接复用。

5.3 146LRU缓存：链表与哈希表的经典组合

LRU缓存严格来说不算纯链表题，但Hot100把它放在链表章节，因为它最经典的实现就是“哈希表+双向链表”。哈希表负责O(1)查找，双向链表负责O(1)删除和移动，两者配合是兼顾时间复杂度和操作完备性的方案。

我用Python给一个可运行版本，把它封装成类：

class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = {} self.head = DLinkedNode() self.tail = DLinkedNode() self.head.next = self.tail self.tail.prev = self.head def _remove_node(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 def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self._move_to_head(node) return node.value def put(self, key, value): if key in self.cache: node = self.cache[key] node.value = value self._move_to_head(node) else: node = DLinkedNode(key, value) self.cache[key] = node self._add_to_head(node) if len(self.cache) > self.capacity: removed = self.tail.prev self._remove_node(removed) del self.cache[removed.key]

用双向链表的原因是删除任意节点时需要知道它的前驱，单链表找前驱要遍历，做不到O(1)。head和tail两个虚拟节点能省掉大量“判断是否为空”的if，让链表的插入删除代码统一。这个工程思维在写缓存、连接池、消息队列这类场景里都很有用，面试官看到你能解释清楚head和tail存在的意义，往往会加印象分。

6. 刷完链表题之后的复盘经验与常见坑

6.1 每一步都画图，或者至少在心里画图

链表题最常见的失败方式，是自以为想清楚了，写出来却发现指针绕成了一个环。我自己的经验是，任何涉及两个以上指针变动的操作，都值得在草稿纸上画出“操作前”和“操作后”两个状态。不需要画得多好，能看出谁指向谁就行。

画完图之后盯住三个位置：当前指针在哪里、当前指针的next是什么、修改后会丢失哪一段引用。以反转链表为例，画一次图你就能理解为什么必须先保存nxt再翻转，不理解的人写十次错十次。刷题不是比谁写得快，而是比谁脑子里有一张可信的“指针地图”。

6.2 递归深度限制与迭代偏好

反转链表、排序链表、K个一组翻转都可以用递归写，但Python的默认递归深度在1000层左右，链表如果很长，递归写法会直接报RecursionError。国内大厂面试手写算法时，很多场合也不喜欢递归，因为你要额外解释调用栈的空间开销。

所以我给你一个偷懒但稳妥的标准：遇到链表题，优先想迭代解法；递归只作为一种可选的备选方案，或者用来让自己理解“子问题”的结构。Hot100里面链表题几乎每道都有自然的迭代写法，没有哪道是“不用递归就做不出来”的。

6.3 内存泄漏与断链问题

在LeetCode刷题阶段不太用担心内存泄漏，但如果你在做毕业设计、实际工程代码或者C/C++题目，断链和内存泄漏就是必须考虑的。链表操作的经典内存问题有两个：删除节点后没有释放节点空间，导致内存泄漏；修改next时没有考虑其他节点的引用，导致内存悬空。

用Python写链表题时会自动管理内存，但你需要明确感知“什么时候该主动断开引用”。比如在删除倒数第N个节点时，slow.next = slow.next.next之后，被删除节点如果还被某个变量引用，它依然存在；如果没有其他引用，Python会自己回收。理解这个引用模型，再去写C++或者面试时讨论内存问题，会顺畅很多。

6.4 我的刷题顺序建议

最后给一份我自己验证过的刷题顺序，适合Hot100链表部分的初学者：先刷206反转链表和21合并两个有序链表，这两道是一切的基础；接着刷141环形链表、876链表的中间结点、19删除链表的倒数第N个结点，练快慢指针；然后刷92反转链表II、234回文链表、82删除排序链表中的重复元素II，这三道会把前面学的技巧组合起来；再刷2两数相加、148排序链表、143重排链表、25 K个一组翻转链表。最后留一道146 LRU缓存作为综合实战。

这个顺序不是按Hot100原本的排列，而是按知识点依赖关系排的。比如不先刷反转链表，直接做回文链表或K个一组翻转，思路会断一截；不先刷中间节点，直接做重排链表也容易卡壳。按这个顺序刷完，链表题在面试中基本不会再成为扣分点。

我自己刷链表题还有一个习惯：每天只集中刷三到四道，但每道题做完之后，会把核心代码手写一遍，写的时候心里默念“先保存后继、再改指针、最后移动”。听起来很基础，但坚持下来之后，很多边界条件错误都在写之前就被排除了，这道题带来的收益也远远超出了题目本身。