链表算法双核心：快慢指针求中间结点与回文链表判定

链表的中间结点和回文链表，是链表算法题里最经典的组合拳。我在刷算法专题的时候，习惯把这两道题放在同一天解决——它们都指向同一个核心技能：快慢指针。回文链表的最优解法，本质上就是“找到链表的中间结点”加上“反转后半段链表”的拼装。这篇文章把两道题的思路推导、代码实现、边界处理和面试追问完整过一遍，适合正在刷链表专题、或者面试前想用几道题串起链表核心套路的开发者。

1. 为什么把“找中间结点”和“回文链表”放在一起练

1.1 两道题的承继关系

876题是234题的前置技能，这句话很多题解讲过，但很少有人具体说明白“前”在哪里。

判断一个链表是不是回文，最朴素的想法是：把链表“对折”，然后一头一尾同时往中间走。数组能做到，因为可以随机访问下标；但单向链表只能从头往后走，没办法从后往前。所以要实现“对折”的效果，第一步必须是找到链表的中点，把链表拆成两半。这就是876题干的事。

第二件事才是关键：后半段链表的方向是反的，直接从头往尾比不行，得先把后半段“掉头”，也就是反转链表。于是234题的解法里，876题的中点和反转链表这两个知识点缺一不可。把两道题连起来练，等于一次吃透三个高频考点：快慢指针、反转链表、双指针比较。

1.2 适合谁来读、读到什么程度

如果你是刚开始刷链表题的新手，建议先自己动手写一遍876题，哪怕是用最笨的“数长度再走一半”的暴力写法，然后再看快慢指针的推导过程。234题可以先只写数组辅助解，把回文判断的逻辑跑通，再逐步升级成“快慢指针+反转后半段”的O(1)空间解法。

如果你是面试前突击，这两道题要达到的状态是：不假思索写出876的快慢指针实现，并且能说清楚循环条件为什么写成while (fast != NULL && fast->next != NULL)；234题要能现场推导出四步走：找中点、反转后半段、比较、恢复原链表。尤其是最后一步恢复链表，很多人在刷题时省略，但面试官大概率会在你写出代码后追问一句：“如果这是线上服务，原链表被你改坏了怎么办？”

2. 876题：链表的中间结点，快慢指针怎么推出来的

2.1 先写一遍暴力解法作为基准

题目要求很简单：给定一个非空单链表，返回它的中间结点。如果链表长度为偶数，有两个中间结点，返回第二个。

我第一次做这题时，第一反应是暴力的两遍遍历。第一遍从头走到尾，统计链表长度n；第二遍从头走n / 2步（整数除法，向下取整），停下来的结点就是答案。

struct ListNode* middleNode(struct ListNode* head) { int n = 0; struct ListNode* p = head; while (p != NULL) { n++; p = p->next; } p = head; for (int i = 0; i < n / 2; i++) { p = p->next; } return p; }

这段代码的时间复杂度是O(n)，空间复杂度是O(1)，逻辑完全正确。但它的问题在于：链表需要完整走两遍。在链表很长、或者链表本身是流式数据只能读一遍的场景下，这个方案就不适用了。

暴力解法最大的价值是提供了一个基准。后面写快慢指针时，可以在本地用同一个测试用例跑这两个版本，验证结果一致。我自己写链表算法时，经常保留一个最朴素的版本当“参照物”，出了 bug 就对拍，定位很快。

2.2 快慢指针的步频推导

快慢指针的思路很像两个人绕着操场跑步：一个人速度是另一个的两倍，同时出发，当快的人跑完全程时，慢的人恰好在一半的位置。

设链表长度为n。慢指针每次走一步，快指针每次走两步。假设快指针到达链表末尾（或越过末尾变成 NULL）时，慢指针一共走了k步，快指针走了2k步。

分两种情况：

• 如果n是奇数，比如n = 2k + 1，此时快指针恰好停在最后一个结点上，走过了2k步，慢指针走了k步，停在第k + 1个结点。这个位置正好是长度为奇数的链表的中点。
• 如果n是偶数，比如n = 2k，此时快指针会越过末尾变成 NULL，同样走过了2k步，慢指针走了k步，停在从头数第k + 1个结点。对于长度为偶数的链表，这正是两个中间结点里的第二个。

所以快慢指针的循环结束条件写成while (fast != NULL && fast->next != NULL)：只要快指针当前不为空，且还能再走两步，就继续让慢指针走一步、快指针走两步。这个条件保证了fast = fast->next->next这行代码不会发生空指针访问。

这个推导值得花时间自己算一遍，因为后面234题里还会用到几乎一模一样的推理，只是循环条件的写法会变。

2.3 边界行为：奇数、偶数、长度1和2

边界条件是最容易翻车的地方，我把几个典型长度手工模拟一遍：

长度1：只有一个结点。进入循环前判断fast != NULL为真，但fast->next == NULL，循环不执行，直接返回唯一结点。正确。

长度2：两个结点。fast指向第一个结点，fast->next非空，进入循环：慢指针走一步到第二个结点，快指针走两步直接变成 NULL。下一轮循环判断fast != NULL为假，退出，返回第二个结点。题目要求偶数长度返回第二个中间结点，正确。

长度3：三个结点。第一轮循环：慢指针到第二个结点，快指针到第三个结点。判断fast->next为 NULL，退出，返回第二个结点。正确。

长度4：四个结点。第一轮循环：慢指针到第二个结点，快指针到第三个结点。此时fast->next非空，进入第二轮：慢指针到第三个结点，快指针到第五个位置即 NULL。退出，返回第三个结点，这是两个中间结点里的第二个。正确。

这四个长度能覆盖所有情况，建议写代码前先在纸上画一遍。

2.4 完整实现与返回“第一个中间结点”的变体

C 语言实现：

struct ListNode* middleNode(struct ListNode* head) { struct ListNode *slow = head; struct ListNode *fast = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

Python 实现：

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

有一个变体题目偶尔会出现：如果链表长度是偶数，要求返回第一个中间结点。做法是把快指针的初始位置改一下，让fast = head->next，慢指针仍然从head出发。

验证长度4：慢指针在第一个结点，快指针在第二个结点。进入循环后慢指针走到第二个结点，快指针走到第四个结点，fast->next为 NULL，退出，返回第二个结点。这个位置是第一个中间结点，正确。这个变体可以用来考察对快慢指针初始化位置的理解，建议顺手练一下。

3. 234题：回文链表，从O(n)空间到O(1)空间的升级

3.1 四种解法横向对比

回文链表的解法，常见的有四种，我按推荐程度排个序：

第一种，复制到数组后双指针比较。遍历链表，把所有结点的值放进数组，然后用两个下标从两端往中间扫。写起来最简单，但空间复杂度是O(n)，而且如果链表很长，数组可能占用大量内存。

第二种，递归加全局指针。利用递归函数一层层压栈的特性，让递归到链表尾部后从后往前返回，外部保留一个从头部开始移动的指针，逐层比较。代码很简洁，但递归深度等于链表长度，链表上万结点时栈容易溢出。

第三种，快慢指针找中点，反转后半段，再逐个比较。时间O(n)，空间O(1)，这是面试官最想要的标准答案。

第四种，反转前半段。找中点过程中直接把前半段反转，然后从两端往中间比。思路可行，但实现起来容易跟后半段反转搞混，不推荐在面试中冒险。

四种方法的对比如下：

我的经验是：面试时先快速说一遍数组解法，表示思路清晰，然后主动说“但这样空间是O(n)，我们可以用快慢指针优化到O(1)”，再把第三种解法写出来。这样既展示了思考过程，又直接命中考点。

3.2 最优解的四步走

回文链表的最优解法可以拆成四步，每一步都不难，但连在一起需要想清楚指针的归属。

第一步，找中点。这里用的循环条件和876题不一样：

struct ListNode *slow = head; struct ListNode *fast = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; }

区别在于876题判断的是fast和fast->next，这里判断的是fast->next和fast->next->next。目的是让慢指针停在“前半段的最后一个结点”上，而不是停在“中间结点”上。

第二步，反转后半段。将slow->next作为后半段的头，调用反转函数：

struct ListNode *secondHalf = reverseList(slow->next);

第三步，比较。用两个指针p1从头开始，p2从反转后的后半段头开始，逐结点比较值。循环条件写成while (p2 != NULL)而不是while (p1 != NULL) && (p2 != NULL)，因为后半段长度一定不超过前半段；奇数长度时，中心结点在前半段末尾，不需要再跟自己做一次无意义的比较。

第四步，恢复链表。这个动作在刷题时可以不做，题目只要求返回布尔值，但面试中做了是加分项：

slow->next = reverseList(secondHalf);

恢复的原理是：secondHalf指向的是已经被反转过的后半段链表，再对它做一次反转，就变回原本的顺序，返回的正好是原来的后半段头结点，接回slow->next后，整条链表恢复原状。

3.3 反转链表内嵌函数的实现细节

反转链表本身是另一道经典题，这里先单独写好一个函数：

struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL; struct ListNode *curr = head; while (curr != NULL) { struct ListNode *next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

最关键的细节是：进入循环后，第一件事就是把curr->next保存到next。因为下一行代码curr->next = prev会把当前结点的 next 指针改掉，如果不提前保存，就再也找不到原来后面的结点了，链表会在这里断掉。

这个函数在回文链表中承担了两次反转：第一次把后半段反转用于比较，第二次把反转后的后半段再反转回去用于恢复。同一个函数用两次，把这个函数写熟，234题的代码量会小很多。

还有一个细节值得注意：第二次调用reverseList(secondHalf)时，secondHalf是反转后的后半段的新头，调用后返回值是原来的后半段头结点。我的代码里直接用这个返回值给slow->next赋值，不要误写成slow->next = secondHalf，那是错的，因为secondHalf此时并不是原顺序的头。

3.4 两个易混淆的循环条件：876 vs 234

这两道题放在一起练最大的价值，就是能直观对比两个快慢指针的循环条件为什么长得不一样。

876题的循环条件是while (fast != NULL && fast->next != NULL)，慢指针最终停在“中间结点”上。偶数长度时，它停的是第二个中间结点，正好是题目要求的答案。

234题的循环条件是while (fast->next != NULL && fast->next->next != NULL)，慢指针最终停在“前半段的最后一个结点”上。偶数长度时，它停的是第一个中间结点；奇数长度时，它停在正中间的那个结点。

为什么234题不能让 slow 停在第二个中间结点？因为下一步要反转slow->next，这个位置必须是后半段的起点。如果 slow 停在了第二个中间结点，后半段就会少一个结点（第一个中间结点被划到前半段末尾了），比较时对应关系全乱。

用一个长度4的链表模拟一遍：链表1 -> 2 -> 2 -> 1，234题的循环只走一次，slow 停在第一个2，也就是前半段1 -> 2的末尾，slow->next指向第二个2，这是后半段的头。反转后半段得到1 -> 2，然后1和1比，2和2比，正确。

如果把876题的循环条件套进来，slow 会走到第二个2，slow->next指向最后的1，反转后只剩1，跟2比，立刻出错。

4. 实操记录：本地构造链表、跑测试用例、修两个坑

4.1 三分钟写一个链表调试工具

刷链表题最痛苦的是没有现成的测试环境，每次都得手工造数据。我在本地写了一套很小的链表工具函数，几百种情况都能快速验证。

struct ListNode* createList(int arr[], int n) { if (n <= 0) return NULL; struct ListNode *head = malloc(sizeof(struct ListNode)); head->val = arr[0]; head->next = NULL; struct ListNode *tail = head; for (int i = 1; i < n; i++) { struct ListNode *node = malloc(sizeof(struct ListNode)); node->val = arr[i]; node->next = NULL; tail->next = node; tail = node; } return head; } void printList(struct ListNode* head) { while (head != NULL) { printf("%d -> ", head->val); head = head->next; } printf("NULL\n"); } void freeList(struct ListNode* head) { while (head != NULL) { struct ListNode *next = head->next; free(head); head = next; } }

三个函数分别负责建表、打印、释放。别小看这个工具，很多链表 bug 是“看不见”的，只能靠打印确认。尤其是在234题里，反转后半段之后、恢复链表之前、恢复链表之后各打印一次，指针有没有接对一目了然。

4.2 用一张用例表把边界全测一遍

我测试时会覆盖下面这些用例，每道题跑一遍，速度和正确性都看：

这几组用例能覆盖所有分支。特别是“双结点回文”和“偶数长度非回文”，前者最容易在循环条件上出错，后者最容易在中点归属上出错。

单结点和空链表在234题里可以直接提前返回 true，因为空链表和只有一个结点的链表天然是回文。代码开头加一行if (head == NULL || head->next == NULL) return true;，可以省掉后面所有边界判断。

4.3 我在调试中踩过的两个坑

第一个坑：876题不小心把循环条件写成了while (fast->next != NULL && fast->next->next != NULL)，也就是直接套用了234题的写法。跑长度4的链表时，返回的是第二个结点而不是第三个结点，测试用例立刻暴露了问题。这个错误特别容易犯，因为两道题连着刷的时候，肌肉记忆会带着手走。

第二个坑：234题反转后半段后，直接比较就返回了结果，没有恢复链表。在对比模式下跑测试时发现，第一次调用isPalindrome后，原链表被改成了“前半段 + 反转后半段”的混合结构，第二次再调用同一段测试数据，结果就不对了。这提醒我：如果算法会改变输入数据，必须在返回前恢复，否则函数不是可重入的。

修完之后，我在返回语句前强制执行slow->next = reverseList(secondHalf);，再打印链表，顺序完全恢复原样。

5. 常见问题排查速查表

5.1 空指针到底怎么防

快慢指针的空指针风险主要在两个地方。一个是循环条件，876题里fast->next必须在fast != NULL成立后再判断。C语言的&&是从左到右短路求值的，只要顺序写对，fast为 NULL 时根本不会执行后半句。

另一个是反转链表时对curr->next的访问。curr本身在循环里已经判过非空，但curr->next可能是 NULL，这时只是把 NULL 赋给prev，没有崩溃风险；真正的风险在于改了curr->next之前没有用临时变量保存原来的next，导致下一次循环找不到后继结点。处理方式是在curr->next = prev之前先取struct ListNode *next = curr->next。

5.2 奇偶判断错了会有什么表现

如果876题要求返回第二个中间结点，但你用了234题的循环条件，偶数长度会返回第一个中间结点。比如1 -> 2 -> 3 -> 4，正确结果是3，写错后返回2，测试用例立刻能抓出来。

如果234题用了876题的循环条件，偶数长度时 slow 会停在第二个中间结点，反转后半段时少算了一个结点，比较时值对不上。观察到的现象是：前半段第一个结点和后半段开头不匹配，即使链表本身是回文，也会返回 false。

我的排查方法是：对长度2、4的偶数链表和长度3、5的奇数链表分别打点输出slow->val，确认 slow 停的位置是否符合预期。

5.3 原链表被改坏了怎么办

234题里，如果省略恢复步骤，函数返回后原链表从slow->next开始就变成反转后的顺序了。这在刷题平台上通常不检查，但一旦函数被复用、或者面试官要求写一个不改变输入数据的函数，这就是硬伤。

恢复的时机有讲究：不能只在返回 true 之前恢复，在发现不相等准备返回 false 的分支里也要恢复。所以我的写法是先比较完，把结果存进一个变量，恢复链表后再返回这个变量。这样不管结果如何，原链表都能保证完整。

bool result = true; while (p2 != NULL) { if (p1->val != p2->val) { result = false; break; } p1 = p1->next; p2 = p2->next; } slow->next = reverseList(secondHalf); return result;

5.4 面试追问清单

这道题常见的追问有这些，提前准备好，面试不慌。

问：空间复杂度能到O(1)吗？答：快慢指针找中点加反转后半段，比较和反转都是常数个指针变量，空间O(1)。

问：如果链表特别长，递归解法会怎样？答：递归深度等于链表长度，长链表可能导致栈溢出；快慢指针的迭代解法没有这个问题。

问：反转链表会不会改变原链表？答：如果只是反转并在比较后恢复，不会；但如果不做恢复步骤，原链表会被永久改变。

问：值类型换成结构体或对象怎么比较？答：比较逻辑不变，只要重定义了“相等”的含义；数组解法里存储整个对象开销会很大，O(1)空间解法的优势更明显。

6. 个人复盘：这组题打通了哪些链表套路

6.1 快慢指针能秒杀的题型

把876和234刷透之后，我发现自己对“快慢指针”这一类问题有了整体认知。快慢指针的两种形态覆盖了链表里一批高频题。

第一种形态是“速度差”，比如876题用两倍速找中点，环形链表的题用快慢指针判断是否有环、找环的入口。第二种形态是“先到先做”，比如删除链表倒数第N个结点，让快指针先走N步，然后快慢指针同步走，快指针到末尾时慢指针正好在待删结点的前一个位置。

还有一类题是“找中点+反转+拼接”，比如重排链表，要求把链表重排成“第一个结点、最后一个结点、第二个结点、倒数第二个结点……”这样的顺序，思路就是找中点、反转后半段、然后交替拼接。这个套路跟234题几乎一模一样，只是最后一步从“比较”变成了“交叉合并”。

所以刷题不必贪多，把一个组合拳打透，能辐射一串题目。

6.2 画图比写代码更重要

我做这两道题耗时最长的地方不是写代码，而是画图。链表题画图模拟非常管用，我会在一个链表图上标出每一步 slow 和 fast 的位置，连续画几轮后，循环条件为什么这么写、边界在哪，都变得很直观。

具体的做法是：先画一个长度为4的链表，每个结点画成方框，slow 和 fast 用两个不同颜色的箭头标记。每执行一次循环，就把箭头移动一次。奇数长度的链表也画一遍，你会发现 “fast 走到 NULL” 和 “fast 走到最后一个结点” 是两种不同的结束方式，分别对应偶数长度和奇数长度。这个认知不靠画图很难建立起肌肉记忆。

6.3 恢复原链表这个动作的工程意义

最后说一个小细节：刷题时恢复链表不是必须的，但我强烈建议养成这个习惯。

面试中，写完234题的标准解法后，主动补一句“我这里的反转会改变原链表，所以比较完要恢复”，整段代码的工程素养立刻体现出来了。这比多写一个边界判断更让面试官印象深刻。

我在实际开发中处理链表时也遵循同样的原则：能不改动传入的数据结构就不改；实在要改，也要保证操作结束后恢复原状。这个原则在算法题里看似多余，在真实系统里却是避免线上事故的基本素养。两道算法题练完，最值钱的收获其实是这一点。