链表的中间结点：快慢指针的推导、边界与工程实践

“链表的中间结点”这个题目我在很多场合都提过。它看起来就是个基础算法题但每次面试候选人、带新人写代码、甚至自己在排查线上链表结构的数据时都会发现这题藏着一堆值得掰开揉碎讲的东西。这次就把我从“看到题”到“写成健壮代码”的过程完整拆开把快慢指针的推导、边界条件的坑、在工程里的真实用途一次说透。无论你是刚学链表、准备算法面试还是写了好几年业务代码偶尔被链表恶心到这篇都应该能给你点新东西。1. 题目拆解一条链表的“中间”到底在哪1.1 为什么不能像数组一样直接取下标很多人第一次接触这题会本能地想数组里取中间元素不就是arr[n/2]吗链表不也类似吗还真不是。数组是一段连续内存知道首地址和下标CPU 一次寻址就能拿到目标元素这叫随机访问。单链表每个结点只是“当前值 下一个结点的指针”想走到第 n/2 个结点你必须从 head 开始一个 next 一个 next 地跳过去这叫顺序访问。这个差别直接决定了链表中间结点问题不能像数组那样“一步到位”。更麻烦的是很多时候你根本不知道链表有多长。你要是问 C 语言里能不能用sizeof(list)求链表长度我劝你趁早忘掉这想法——sizeof只能算结构体本身的字节大小它管不到你动态分配的几百个结点。所以链表题的第一步永远是别总想着随机访问想着怎么用指针移动来解决问题。1.2 中间结点的定义奇数与偶数两种情况题目的基本定义是给定一个非空单链表返回它的中间结点。但“中间”这个说法有个隐藏歧义——链表结点总数是奇数时正中间那个结点没争议如果是偶数个结点中间有两个候选偏左那个、偏右那个。很多在线判题系统默认偶数长度时返回到中间偏右的结点。比如四个结点1-2-3-4中间偏右就是 3。但也有题目或者面试官约定返回偏左也就是 2。你说这算不算坑当然算。面试时你直接开写很可能辛辛苦苦把代码写完面试官问一句“偶数个结点你返回的是哪个”你才发现两人对题意的理解根本不一样。所以拿到这题第一件事不是写代码而是确认输入约束和输出约定链表是否非空、偶数长度返回偏左还是偏右、能不能用额外空间。这只是一个小题目但这个习惯放到真实需求里非常重要需求歧义是项目返工的头号原因。1.3 标准的单链表结点长什么样后续所有代码都会基于这个最基础的结构struct ListNode { int val; struct ListNode *next; };比如建一个结点struct ListNode *node (struct ListNode *)malloc(sizeof(struct ListNode)); node-val 1; node-next NULL;需要强调的是这里讨论的单链表不带头结点head直接指向第一个数据结点。带头结点的链表多一个 dummy 结点算法思路一样但 head 的语义变了写代码时要注意区分。工程上有人喜欢带头结点有人不喜欢取决于有没有删除头结点的需求。2. 三条解法的思路对比你会用哪一种2.1 解法一两次遍历先数长度再定位最直观的思路就是第一遍从头走到尾数出链表总长度 n第二遍再走 n/2 步停下来的结点就是中间结点。从代码角度说这个方法几乎不会写错struct ListNode* middleNode(struct ListNode* head) { int count 0; struct ListNode *cur head; while (cur) { count; cur cur-next; } cur head; for (int i 0; i count / 2; i) { cur cur-next; } return cur; }优点很明显简单、直观、不容易踩空指针的坑。缺点是要遍历两遍。如果你的数据是“一次性数据流”比如只能从头到尾读一遍就从内存消失的日志记录这个方法直接废掉。时间复杂度 O(n)空间复杂度 O(1)。对于小链表完全够用面试时如果你一时没想到快慢指针先给出这个解法也没问题至少证明你具备最基础的链表遍历能力。2.2 解法二用数组存结点用下标取中间还有一种很“偷懒”的办法遍历一次链表把每个结点的指针都塞进一个数组或列表然后直接list[idx/2]返回。def middleNode(head): nodes [] cur head while cur: nodes.append(cur) cur cur.next return nodes[len(nodes) // 2]犟一句这个方法本身不是错很多场景下它甚至是最实用的。但它引入了 O(n) 的额外空间。面试官大概率会追问一句“能不能不用额外空间”如果你接不上来就会显得你只会背答案。所以它通常是过渡思路用来反衬快慢指针的优雅。2.3 解法三快慢指针一次遍历拿到中点快慢指针的思路一句话就能说完让慢指针每次走一步快指针每次走两步当快指针走到链表末尾时慢指针刚好停在中间位置。从直觉上理解这是一个“速度差”问题。快指针速度是慢指针的两倍同一时间内快指针走过的路程就是慢指针的两倍。快指针走完整条链表时慢指针自然走了半条。不需要先知道链表有多长也不需要额外空间边遍历边定位一次搞定。三种方法对比如下解法时间复杂度空间复杂度遍历次数适用场景两次遍历O(n)O(1)2次链表长度已知、允许二次遍历数组存储O(n)O(n)1次允许额外空间代码最短快慢指针O(n)O(1)1次只能遍历一次、空间受限、面试首选面试聊这题时我通常先主动把这三种方案的取舍都摆出来再写快慢指针。一是展示思路广度二是让面试官知道你不仅能写代码还知道为什么选这个方案。3. 手把手实现快慢指针从画图到代码3.1 双指针移动的边界条件详解快慢指针的核心代码不长但边界条件写错的人相当多。标准实现是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; }循环里慢指针走一步快指针走两步。那么问题来了循环条件为什么是fast ! NULL fast-next ! NULL而不是只判断fast-next因为快指针一次要跳两步如果fast-next已经是空再取fast-next-next就是对空指针解引用程序直接崩溃。所以第二个判断必须在第一个判断之后“确保 fast 本身非空并且 fast 的下一个结点也非空”这是一个先判自己、再判邻居的顺序问题。拿纸笔画一下就清楚了。假设链表有 5 个结点下标 0 到 4初始 slow0fast0。第 1 轮slow1fast2。第 2 轮slow2fast4此时fast-next为 NULL循环停止。返回 slow2正好是中间结点。假设链表有 6 个结点下标 0 到 5初始 slow0fast0。第 1 轮slow1fast2。第 2 轮slow2fast4。第 3 轮slow3fast6NULL此时fast NULL循环停止。返回 slow3对应中间偏右的结点。也就是说上面这段标准代码返回的是偶数长度时的中间偏右结点。这个约定和绝大多数在线判题系统一致。3.2 为什么是走两步不是走三步四步有人可能会想快指针走快一点是不是也不影响慢指针停在中间听起来好像只要快指针走到末尾慢指针总会停在中点。但仔细算一笔账如果快指针每次走 3 步那同一时间内慢指针只走了快指针三分之一的距离快指针到末尾时慢指针停在大约三分之一处而不是一半。对于“找中间结点”这个需求快指针必须是慢指针速度的 2 倍。速度比 2:1 是数学上的硬约束。那有没有可能让快指针先跑一段再用 1:1 的速度跑这当然可以但那就退化成“先定位到某个参考点再匀速前进”的做法本质上还是需要多一次定位计算不如 2:1 直接省事。3.3 三种主流语言实现C、Python、CC 语言版本已经在上面给过了这里补充 Python 和 C。Python 的链表定义通常用类class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def middleNode(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slowPython 里面fast and fast.next利用短路求值fast为空时整个表达式直接为空不会执行后面的取值所以写起来很干净。C 版本class Solution { public: ListNode* middleNode(ListNode* head) { ListNode *slow head, *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; } };三个语言本质完全一样区别只在空指针表达C 用NULL/0C 用nullptrPython 用None。3.4 如果想返回中间偏左怎么写实际开发里偶尔会要求“取中间靠左”或者“前半段不要包含中间结点”尤其在归并排序切分链表时你往往需要把链表切成尽量均匀的两段。这时候标准快慢指针返回的“偏右”结点会让你切出的左半段比右半段长不符合某些场景的预期。想拿到中间偏左的结点只需要把循环条件收紧一层struct ListNode* middleLeftNode(struct ListNode* head) { if (head NULL) return NULL; struct ListNode *slow head; struct ListNode *fast head; while (fast-next ! NULL fast-next-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }验证一下4 个结点0,1,2,3fast 经过一轮后走到 2发现fast-next-next为空循环结束slow 停在 1是中间偏左6 个结点0..5fast 两轮后走到 4发现fast-next-next为空循环结束slow 停在 2也是偏左。注意这里我在进入循环前做了head NULL的判断因为后面要访问fast-next-next空链表会直接崩溃。这种差异很细微但正是这些细微之处决定了代码是不是“工程级”。4. 从一道题到一个技巧快慢指针的工程化运用4.1 同一个套路还能做链表环检测快慢指针不止能找中点。另一个经典应用是判断链表有没有环让慢指针每次走一步快指针每次走两步如果链表中存在环快指针最终会绕回追上慢指针如果没环快指针会先走到 NULL。这个思路和找中间结点看着像本质不同。找中间结点是利用 2:1 的速度让慢指针精确停在中点环检测是利用 2:1 的速度差制造“追及”快指针绕圈时每次都比慢指针多走 1 个结点只要环存在它们迟早相遇。所以当你掌握了快慢指针的底层逻辑——两个指针以不同速度遍历同一个结构——就会发现它是个通用工具不是一道孤立的题。4.2 归并排序与回文判断中间结点是基石做链表的归并排序第一步就是把链表从中间拆成两半。这也是中间结点问题一个特别经典的落地场景。拆的时候你需要拿到“前半段最后一个结点”或者“后半段第一个结点”这种情况下我一般会结合middleLeftNode再加一个next指针把链表真正切成两个独立链表。回文链表的判断思路也常用中间结点先找到中间结点然后把后半段链表反转再遍历对比前半段和反转后的后半段。没有中间结点这个思路根本没法落地。可以说中间结点是很多链表复杂操作的“地基”这就是为什么面试官总爱拿这题试探候选人——它能快速反映你对链表遍历、指针操作、边界条件的综合熟悉程度。4.3 真实工程场景只知道链表头、不知道总长度有人觉得链表只是在面试题里出现实际开发很少自己写链表。这话对了一半链表确实是 STL 容器和业务框架的底层但你总会遇到需要自己维护链式结构的场景。比如一个不断追加日志的缓冲队列数据量很大且不允许你停下来遍历两次去数长度你就需要一种手段“顺便”拿到当前数据量的中间位置做抽样。在 C 语言嵌入式开发里串口数据缓冲经常用链表做队列较长时取中间结点做水位分析这时候链表的总长度仍在变化快慢指针这种一次遍历就能给出近似中间位置的算法就很实用。更重要的是这个场景给了你一种思维模型当数据只能单向读取、长度未知、希望一次遍历时双指针是一个又快又省的答案。5. 面试现场与常见问题速查5.1 面试官会在哪些地方“埋雷”一个候选人写快慢指针面试官通常会在以下几个点上追问如果链表为空你的代码会怎样——标准写法里while (fast fast-next)head 为空时循环不执行返回 NULL正好绕过问题。如果只有一个结点——返回 head 本身。如果有两个结点——返回值是偏右那个你需要清楚自己的约定。如果链表特别长你的指针会不会有溢出风险——不会指针只是移动不涉及数值累加。如果要求返回中间结点的前一个结点呢——用额外指针 prev 跟随 slow循环结束时 prev 就是答案。我建议你把这些答案在脑子里过一遍再写代码。代码写完主动跟面试官提一句边界条件的验证结果印象分会明显不一样。5.2 我见过的错误写法与分析这题我在面试和 code review 里见过不少翻车写法列几个典型的条件顺序写反。写成while (fast-next fast)看起来差不多实际上当 fast 为 NULL 时会先执行fast-next直接解引用空指针程序崩溃。只判断fast-next不判断fast。快指针走两步时如果 fast 正好停在倒数第二个结点fast-next-next就是空指针照样崩。让快指针走三步或更多。结果慢指针停在大约三分之一处完全偏离题意。用数组存储后回答“空间复杂度是 O(1)”。这一看就没想过内存占用比没写出来更尴尬。这些错误本质都是对指针生命周期和循环不变量的理解不够清晰。写这类代码时心里始终要有一条“指针移动路径图”每一步之后每个指针指向哪里必须一目了然。5.3 常见问题速查表问题原因解决办法空链表崩溃访问了空指针的 next循环条件写成fast fast-next返回了错误的“中间”偶数长度约定没确认明确返回偏左还是偏右选择不同循环条件快指针走两步时空指针异常只判断了 fast 没判断 fast-next两个条件必须同时判断顺序不能颠倒空间复杂度被质疑用了数组存储结点改用快慢指针空间降到 O(1)慢指针没能停在中间快慢指针速度比不是 2:1快指针每次走两步慢指针每次走一步这张表基本覆盖了你能碰到的所有坑。6. 验证与扩展如何用测试用例证明算法正确6.1 构造不同长度的链表来测代码写出来不测等于白写。我的习惯是构造长度从 0 到 7 的链表分别验证。0 就是空链表1 到 7 分别覆盖奇数和偶数情况。像下面这样写一个简单的构造函数struct ListNode* createList(int arr[], int len) { if (len 0) return NULL; struct ListNode *head (struct ListNode *)malloc(sizeof(struct ListNode)); head-val arr[0]; head-next NULL; struct ListNode *cur head; for (int i 1; i len; i) { struct ListNode *node (struct ListNode *)malloc(sizeof(struct ListNode)); node-val arr[i]; node-next NULL; cur-next node; cur node; } return head; }然后逐个打印中间结点的值。5 个结点时中间结点是索引 26 个结点时标准实现返回索引 3。如果你觉得肉眼看不直观可以在中间结点处打印slow-val对比预期值即可。6.2 偏左和偏右如何切换前面已经写了两个版本的代码这里再总结一下记忆方法返回偏右while (fast fast-next)快指针每次能走两步就走两步偶数长度时慢指针停在偏右位置。返回偏左while (fast-next fast-next-next)要求快指针还能再走两步才会继续偶数长度时慢指针停在偏左位置。返回中间的前一个结点用 prev 指针记录 slow 的上一个位置循环结束后返回 prev。这三个变体解决的是同一类需求的不同“偏移量”问题面试时如果能主动说出它们的使用场景会给面试官留下“这人真的理解链表”的印象。6.3 再往前走一步倒数第 k 个结点和 1/k 处结点掌握了快慢指针你会发现自己还能解很多同类题。比如找链表倒数第 k 个结点快指针先走 k 步然后快慢指针以相同速度前进当快指针走完时慢指针就停在倒数第 k 个位置。这其实还是“速度差”思路的变体只不过这次是先制造一个 k 的距离差再用同速保持这个差值。如果想找的是“链表的 1/3 处”呢理论上可以构造 3:1 速度的快慢指针但要注意整数步数带来的舍入偏差。链表长度不是 3 的倍数时慢指针停的位置不一定是严格的 1/3。所以这个推广更多是近似不适合屈服精度要求的场景。这些扩展题都能加深你对链表“顺序访问”特性的理解。回头再看“链表的中间结点”它真的不只是让你背一个模板而是帮你建立“怎么用指针移动解决定位问题”的思维。最后说点我自己的习惯。每次写完链表相关代码我都会在注释里记下这组边界测试的结论空链表返回空、单结点返回自身、偶数长度确认偏左偏右。这几个结论记牢了链表题基本不会翻车。遇到过太多次线上问题最后定位到“链表边界没处理”也带过不少新人写链表代码发现大部分 bug 不是算法错而是“以为自己想清楚了边界其实没有”。把这题吃透对你写任何链表相关代码都会有帮助。