企业官网建设流程全解析

链表专题在力扣 hot100 里看着题不多，真刷起来却最容易让人怀疑自己到底有没有学过编程。尤其是刷到（二）这个阶段，两两交换、区间反转、K 个一组翻转、排序链表、重排链表、回文链表、奇偶链表，没有一道是单纯考 API 的，全是基础操作的组合。上一篇笔记整理了反转、合并、环形链表、相交链表这些基础题，这篇继续把剩下的进阶题拆开讲，顺带把我实际写代码时反复翻车的地方一起整理出来，给正在刷链表专题的朋友一条可以直接照着练的路线。

如果你刚看完链表基础，建议先把上一篇的题过一遍再进这篇。因为这篇里几乎所有题目都默认你会了“完整反转链表”和“合并两个有序链表”，这两个基本功不熟的话，后面会很吃力。

1. 链表题的核心打法：先想清三件事

1.1 为什么看答案都懂，自己写就断链

链表题最迷惑人的地方在于：代码看起来就那么几行，变量名全是 next、prev、cur、dummy，一不留神就不知道谁指向谁了。数组和链表最大的区别是内存结构不同。数组是一段连续内存，改元素只是覆盖下标；链表每个节点离散存储，一个节点里既存值又存指针，修改指针的顺序错一步，轻则丢一段节点，重则原地形成环。

我见过很多朋友刷链表题的状态是：打开题解，觉得“我懂了”，合上代码，自己写就卡在第一步。原因基本不是逻辑不懂，而是没在动手前把“先断哪根链、再接哪根链”这个顺序想清楚。举个最简单的例子，反转链表时如果你先执行cur.next = prev，那 cur 原来的后继就找不到了，后面的节点全部失联。所以链表题的第一步永远是：先保存后继，再改指针。这不是技巧，是保命习惯。

另一个容易踩的点是空指针。链表题特别喜欢考head == null、head.next == null这些边界。循环条件里如果写成while (fast.next != null && fast != null)，顺序反了，fast 为 null 时会直接空指针。先把节点本身是不是 null 判断掉，再判断它的 next，这是我前面刷题总结出的硬规矩。

链表题本质上考的不是“会不会用 API”，而是你对“引用”这个概念的理解深度。写的时候要把自己当成在摆弄一列火车车厢：每一节车厢只知道自己下一节是谁，你想重排整列车，必须保证每次摘挂操作都有一只手抓着待操作的节点，否则就是事故现场。

1.2 三板斧：哑节点、快慢指针、头插法

链表进阶题虽然花样多，但打来打去就是三招。

第一招是哑节点，也就是dummy。凡是头节点可能被修改的题，几乎都能用ListNode dummy = new ListNode(0); dummy.next = head;把头节点的处理统一掉，最后返回dummy.next即可。两两交换、区间反转、K 个一组翻转、合并两个有序链表，全都可以用这个套路。它的价值在于你不用单独写“如果头节点被换掉了怎么办”的特殊分支，代码结构会干净很多。

第二招是快慢指针。快指针每次走两步，慢指针每次走一步，快指针到达末尾时慢指针刚好在中点附近。这个技巧用在找中点、判环、找倒数第 N 个节点上都非常好使。但要注意快指针的初始位置不同，慢指针落点会差一两个节点，这一点直接影响后面“从哪一段开始反转”，我在第 3 章会专门展开。

第三招是头插法，也叫局部反转。用 prev、cur、next 三个指针，不断把 cur 后面的节点摘出来插到 prev 后面，就能在 O(1) 额外空间内完成一段链表的原地反转。理解了这套操作，反转链表 II、K 个一组翻转、重排链表、回文链表都会变得很顺。

所以说，链表进阶题看起来每题都是新题，其实大多是这三招的组合。做题的时候先问自己：这题要不要换头？要不要找中间点？要不要反转某一段？把这三个问题想明白了，思路基本就出来了。

1.3 边界条件与复杂度是隐藏考点

链表题的价值往往不在主路径，而在边界。一道题你能写出主逻辑，面试官接下来一定会问：如果链表是空呢？只有一个节点呢？长度是奇数或偶数呢？如果递归深度太深怎么办？这些就是拉开差距的地方。

另一个绕不开的是复杂度。链表不支持随机访问，查找只能从头遍历，所以 O(n) 时间往往就是下限。至于空间复杂度，很多刷题的人默认 O(n) 也能接受，但面试里经常会追问“能不能做到 O(1) 额外空间”，这时候就要清楚递归带来的栈空间也算额外空间。比如 K 个一组翻转和归并排序链表，递归写法简洁，但递归栈会消耗空间；如果面试官较真，你得能给出迭代版本。

我的建议是：刷链表题时每做完一题，都顺手在笔记里写上时间复杂度和空间复杂度，并且区分“递归版”和“迭代版”。不然到面试时被追问优化方案，容易当场卡壳。

2. 四道高频题逐个拆解

这一阶段我会按从易到难的顺序拆四道题：两两交换、区间反转、K 个一组翻转、排序链表。先放一张速查表，方便你后面回头对照。

2.1 两两交换链表中的节点

题目要求把相邻两个节点交换，1->2->3->4 变成 2->1->4->3。最容易想到的办法是直接交换节点里的值，但面试官真正的考点是指针的连接关系，所以还是踏踏实实做节点交换。

我推荐的写法是哑节点加迭代，核心逻辑是每次处理一对节点，然后跳转到下一对：

public ListNode swapPairs(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (prev.next != null && prev.next.next != null) { ListNode first = prev.next; ListNode second = first.next; first.next = second.next; second.next = first; prev.next = second; prev = first; } return dummy.next; }

模拟一下 1->2->3->4。第一次进入循环时，first 是 1，second 是 2。先把 first.next 指向 3，再把 second.next 指向 first，最后把 prev.next 指向 second。到这里链表已经是 dummy -> 2 -> 1 -> 3 -> 4。然后 prev 移到 first，也就是节点 1，准备处理下一对。第二次循环处理 3 和 4，过程完全一样。

这个题的坑主要在顺序。如果你先写second.next = first，这时候 first 的原始后继 3 还没被保存，节点 3 和后面的节点就丢了。所以一定要先执行first.next = second.next，把后面的链表“抓住”。另外，循环结束后 prev 要移动到 first，而不是 second。很多初学者在这里忘记移动 prev，导致只交换了一对就退出了。这个题虽然简单，但能把哑节点和指针更新的节奏都练到。

2.2 反转链表 II：指定区间反转

这题要求反转从 left 到 right 的区间，比如 1->2->3->4->5，反转 2 到 4 得到 1->4->3->2->5。它比全链表反转难在：你只反转中间一段，前后的连接关系还要保住。

我的写法是哑节点加头插法：先定位到 left 前一个节点 pre，然后用头插法把区间内的节点一个一个插到 pre 后面。

public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode pre = dummy; for (int i = 1; i < left; i++) { pre = pre.next; } ListNode cur = pre.next; for (int i = left; i < right; i++) { ListNode next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } return dummy.next; }

解释一下头插法的过程。初始时 pre 指向 1，cur 指向 2，链表是 1->2->3->4->5。第一次循环，next 取到 3，把 cur.next 指向 4，再把 3 插到 pre 后面，链表变成 1->3->2->4->5。第二次循环，next 取到 4，把 cur.next 指向 5，再把 4 插到 pre 后面，变成 1->4->3->2->5，完成。

为什么用头插法而不是先把区间断开再反转？因为头插法始终只需要保存 next 一个变量，不需要记录区间尾节点和它的后继，逻辑上不容易漏。循环次数是right - left，比如区间长度是 3，反转区间内需要插两次，这个细节常有人搞错。left 为 1 时，pre 就是 dummy，正好考验哑节点是否用对了。

2.3 K 个一组翻转链表

这一题的难度一下子会上来。它要求每 K 个节点一组反转，不足 K 个的保持原样，比如 k=2 时 1->2->3->4->5 变成 2->1->4->3->5。

最干净的写法其实是递归。递归的切入点很自然：先扫描 K 个节点，找到本组结尾；如果不够 K 个，直接返回 head；够的话反转本组，然后递归处理剩下的链表，再把本组头节点接到递归结果上。

public ListNode reverseKGroup(ListNode head, int k) { ListNode cur = head; int count = 0; while (cur != null && count < k) { cur = cur.next; count++; } if (count < k) { return head; } ListNode prev = null; ListNode node = head; while (node != cur) { ListNode next = node.next; node.next = prev; prev = node; node = next; } head.next = reverseKGroup(cur, k); return prev; }

思路里最关键的变量是 cur。第一段循环让 cur 停在下一组的开头，所以后面反转本组时，循环条件是node != cur，反转完本组后，原本的 head 变成了本组末尾，它的 next 就接上递归处理后的下一组。

很多第一次写的人会在“递归返回的东西到底接给谁”这里卡住。记住一句话：反转前，head 是本组第一个节点；反转后，head 变成了本组最后一个节点，所以要head.next = reverseKGroup(cur, k)，而新的头是 prev。

另外提醒一句，这个递归版本空间复杂度是 O(n/k) 左右的递归栈。如果面试官明确要求 O(1) 额外空间，就需要改成迭代版。迭代版的核心是维护 preTail 和 nextHead 两个指针：每次先让 end 走 K 步，然后把 start 到 end 这一组反转，再接回 preTail，再把 preTail 移到反转后的末尾。思路不复杂，但写起来需要多记几个变量，建议自己动手实现一遍。

2.4 排序链表：不让用数组怎么办

数组排序很方便，链表排序很多人第一反应是“把链表转成数组，排完序再转回去”，但这样既不满足 O(1) 空间要求，也不是在考链表。链表的归并排序不需要额外数组，因为链表本身就是通过断开和重连指针来排序的。

自顶向下归并的思路是：用快慢指针找到链表中点，把链表切成两半，递归排序两半，再用合并两个有序链表的方法把它们接起来。

public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode rightHead = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(rightHead); return mergeTwoLists(left, right); } private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode p = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; } p = p.next; } p.next = (l1 != null) ? l1 : l2; return dummy.next; }

这里快慢指针为什么fast = head.next？因为我们要找的是“左半段的结尾”，而不是严格的中点。对于 1->2->3->4，slow 会停在 2；对于 1->2->3->4->5，slow 会停在 3。这样保证左半段至少不比右半段短，切分稳定。

不过，自顶向下递归的空间复杂度是 O(log n)，原因是递归栈。LeetCode 这道题的 Follow Up 问的是 O(1) 空间，严格来做要写自底向上的迭代归并。核心思路是：先统计链表长度 n，然后 step 从 1 开始翻倍，每一轮把链表按 step 长度切成若干段，两两合并，再扩大 step。这是链表版的“分段合并”，代码会多一些，但掌握之后很值。

public ListNode sortListIterative(ListNode head) { if (head == null || head.next == null) return head; int n = 0; for (ListNode p = head; p != null; p = p.next) { n++; } ListNode dummy = new ListNode(0); dummy.next = head; for (int step = 1; step < n; step <<= 1) { ListNode prev = dummy; ListNode cur = dummy.next; while (cur != null) { ListNode left = cur; ListNode right = split(left, step); ListNode next = split(right, step); prev = merge(left, right, prev); cur = next; } } return dummy.next; } private ListNode split(ListNode head, int step) { if (head == null) return null; for (int i = 1; head.next != null && i < step; i++) { head = head.next; } ListNode next = head.next; head.next = null; return next; } private ListNode merge(ListNode a, ListNode b, ListNode tail) { while (a != null && b != null) { if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; } tail = tail.next; } tail.next = (a != null) ? a : b; while (tail.next != null) { tail = tail.next; } return tail; }

这个方法的核心是 split 和 merge 的配合。split 负责把当前链从头开始切出 step 个节点，并把这一段和后面的链表断开；merge 负责把两段有序链表合并，并接到上一轮合并结果的尾部。cur 则指向下一段还没处理的链表的头。整个流程不涉及递归，空间复杂度确实是 O(1)。

如果你不想背这么长的迭代版，至少要把递归版写熟，因为大部分面试场景下递归版已经能过。但如果对方追问“能不能不用递归”，你能直接掏出迭代版的思路，印象分会高很多。

3. 三道综合题：同一个套路反复用

重排链表、回文链表、奇偶链表这三道题，表面看需求完全不同，骨子里都是同一个套路：找中点、拆链表、反转后半段、再合并或比较。把这三题放在一起刷，能很直观地体会到“排列组合”式的刷题法。

3.1 重排链表

重排链表要求把 L0->L1->...->Ln 变成 L0->Ln->L1->L(n-1)->...，也就是首尾交替。比如 1->2->3->4 变成 1->4->2->3，1->2->3->4->5 变成 1->5->2->4->3。

思路分三步：先用快慢指针找到中间位置，把链表切成两半；然后把后半段反转；最后把前半段和反转后的后半段交叉合并。

public void reorderList(ListNode head) { if (head == null || head.next == null) return; ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode second = reverse(slow.next); slow.next = null; ListNode first = head; while (second != null) { ListNode nf = first.next; ListNode ns = second.next; first.next = second; second.next = nf; first = nf; second = ns; } } private ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; }

这里快慢指针的循环条件是fast.next != null && fast.next.next != null，不是上一章排序链表里那种fast = head.next的写法。原因是我们希望 slow 停在“前半段的最后一个节点”：长度是奇数时，slow 停在中间节点；长度是偶数时，slow 停在左半段末尾。这样slow.next才是真正的后半段起点。

合并部分的循环条件写成while (second != null)就够了，因为后半段长度最多和前半段一样，反转后不会比前半段长。合并时每次都要先把 first 和 second 各自的下一跳保存下来，再改指针，不然交叉到一半就丢了。这题最容易犯的错误是忘了slow.next = null。如果不把两段断开，合并后会在中间形成一个环，测试时直接超时。

3.2 回文链表

回文链表要求判断链表是否中心对称，比如 1->2->3->2->1 是回文，1->2->3>4 不是。进阶要求是 O(n) 时间和 O(1) 空间，所以把链表转成数组再双指针的做法虽然能过，但不算真正满足题意。

正经做法和重排链表很像：找中点，反转后半段，然后双指针比较。

public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode second = reverse(slow.next); ListNode p1 = head; ListNode p2 = second; while (p2 != null) { if (p1.val != p2.val) { return false; } p1 = p1.next; p2 = p2.next; } return true; }

这里找中点的方式和重排链表完全一致，slow 是左半段末尾。反转slow.next之后，p2 指向反转后半段，p1 指向原始头。当链表长度为奇数时，中间节点不需要比较，因为它对称轴就是它自己，所以循环条件只看 p2 是否为 null。长度为偶数时，p2 长度等于 p1 长度，也能完整比较完。

这个题有个更省心的做法：边走边反转前半段，一次遍历就能完成，但理解起来不如“找中点 + 反转”直观。我建议先把标准解法写熟，再去看进阶写法。另外，如果面试官要求“不能修改链表结构”，比较完再把 second 反转回去即可，也就是再调一次 reverse。大多数人不写这一步也不影响 LeetCode 通过，但面试时主动说明“如果要求保持原链表，我可以在结束后恢复”会很加分。

3.3 奇偶链表

奇偶链表的要求很特别：把下标为奇数的节点排在一起，下标为偶数的节点排在一起，最后奇数段接偶数段。比如 1->2->3->4->5 变成 1->3->5->2->4，而且要求 O(1) 空间、O(n) 时间。

很多第一次做这题的人会去想“节点值奇偶”，但题目说的是节点位置，不是值。做法是用两个指针 odd 和 even 分别串起奇数位和偶数位节点，然后首尾相接。

public ListNode oddEvenList(ListNode head) { if (head == null) return head; ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; while (even != null && even.next != null) { odd.next = odd.next.next; odd = odd.next; even.next = even.next.next; even = even.next; } odd.next = evenHead; return head; }

模拟 1->2->3->4->5。第一次循环：odd.next 从 2 改成 3，odd 走到 3；even.next 从 3 改成 4，even 走到 4。第二次循环：odd.next 从 4 改成 5，odd 走到 5；even.next 从 5 改成 null，even 走到 null。循环结束，odd.next 指向 evenHead，也就是原来的 2，链表变成 1->3->5->2->4。

这题最关键的是循环条件里判断的是 even 和 even.next，而不是 odd。因为 even 每次走两步，如果 even 是 null 或者 even.next 是 null，说明后面没有成对的节点了，再往下走就会空指针。另外，evenHead 必须在 even 被移动前保存，最后奇数段要接的就是最开始那个偶数节点。这个题虽然代码短，但很能检验你对“同时维护两条链”的掌控力。

4. 刷题现场：五个常犯错误与调试方法

4.1 五个一写就错的点

链表题翻车的地方其实很集中，我把高频错误整理成五个，刷题前过一遍能帮你省很多时间。

第一，头节点被修改了，但最后返回了旧的 head。最简单的解法就是哑节点，统一用 dummy.next 返回。不要觉得 dummy 多此一举，它能消灭掉这一类问题。

第二，反转时忘了保存后继。经典场景是写cur.next = prev之前没有用一个 next 变量保存 cur 原本的下一跳。记住口诀：改指针前先保存后继。这个顺序在递归和迭代里都适用。

第三，循环条件里空指针。写快慢指针时，一定要先判断当前节点不为 null，再判断它的 next。while (fast != null && fast.next != null)和while (fast.next != null && fast != null)看起来差不多，运行起来一个安全一个直接崩。

第四，没有断开前后两段。重排链表、排序链表、回文链表都需要把链表切成两段，切完不写slow.next = null，两段还是连在一起，合并时就会出现环，程序跑超时还不容易看出原因。

第五，指针更新位置不对。比如两两交换里，prev 应该移到 first；反转链表 II 里，每次循环结束后 cur 不要乱动；K 个一组翻转里，递归返回的节点要接对。这种问题靠背代码没用，一定要自己手动画图。

4.2 调试链表题的三个习惯

链表不像数组，直接把数组打印出来就能看到内容。链表打印的是节点地址，排错体验很差，所以我写链表题基本都带一个辅助函数：

private void printList(String label, ListNode head) { System.out.print(label + ": "); ListNode cur = head; int count = 0; while (cur != null && count < 20) { System.out.print(cur.val + " -> "); cur = cur.next; count++; } System.out.println("null"); }

加一个count < 20的防御条件非常关键，万一链表成环了，不会无限打印下去。调试时看到输出停在某个节点反复循环，基本可以断定这里形成了环。

第二个习惯是准备标准小样例手推。我会固定用三组样例测所有链表题：空链表、单个节点、3 个节点、4 个节点、5 个节点。3 个节点考验奇数情况，4 个节点考验偶数情况，5 个节点能看出重排和回文里的中间节点处理方式。很多边界错误靠小样例跑一遍就能暴露。

第三个习惯是打印节点身份而不是节点值。判断两个指针是否指向同一个节点时，打印 val 不够，因为两个不同节点可以有相同的值。在 Java 里用System.identityHashCode(node)，在 C++ 里直接打印节点地址，就能清楚看出引用关系。这个方法在调试“是否成环”和“是否断链”时非常有用。

4.3 面试中的节奏控制与沟通话术

刷题最终要过面试这一关，所以顺便聊聊面试节奏。

看到链表题，先别急着写代码。先和面试官说清楚自己的整体思路，比如“这道题我会先找中点，然后把后半段反转，再合并两段”。这样就算后面代码写错，至少让对方看到你有完整方案。

写代码前主动确认边界。比如问一句“如果输入是空链表，直接返回 null 对吧”，既体现了细致，也给自己留出思考时间。写完后主动说复杂度：“时间复杂度 O(n)，额外空间 O(1)”。链表题的空间复杂度很容易被忽略，主动说会显得你更专业。

如果面试官问“能不能优化”，不要一上来就说“不会”。先想想递归版能不能改成迭代版，数组版能不能改成指针版。链表题优化方向基本就是两个：省空间、省遍历次数。比如回文链表先转数组再比较，空间是 O(n)，改成快慢指针加反转就是 O(1)，这个优化路径很典型。

我在实际刷题中还有一个体会：链表题特别适合用“讲题”的方式来检验自己的掌握程度。每做完一题，试着不用代码、只用语言把整个指针移动过程讲给别人听。如果能讲清楚，这题才算真正会了。到面试时，你会发现这种表达能力本身就是很大的优势。