LeetCode 876 题解GoMiddle of the Linked List 链表中点查找与快慢指针实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 876 题「Middle of the Linked List链表的中间结点」展开基于 LeetCode-Go 仓库中该题的完整实现讲解如何使用快慢指针在一次遍历内定位单链表的中点并分析偶数长度链表时返回第二个中间结点的边界处理逻辑。读完本文你将掌握快慢指针技巧的推导过程、Go 语言中的链表数据结构与测试写法并理解该技巧在归并排序148. Sort List、环形链表检测141. Linked List Cycle等经典题目中的复用价值。题目背景与要求原题描述给定一个非空单链表其头结点为head返回链表的中间结点。如果链表长度为奇数返回唯一的中间结点如果链表长度为偶数存在两个中间结点返回第二个中间结点。输入输出示例示例 1奇数长度Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judges serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val 3, ans.next.val 4, ans.next.next.val 5, and ans.next.next.next NULL.示例 2偶数长度Input: [1,2,3,4,5,6] Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, we return the second one.注意给定链表的结点数介于 1 到 100 之间。题目大意中文解读输出链表中间结点。如果链表长度是奇数输出中间结点本身如果链表长度是偶数双数输出中位数后面的那个结点。例如[1,2,3,4]的中间结点是第 3 个结点值为 3。快慢指针解题思路这道题有一个很简单的做法用 2 个指针只遍历一次就可以找到中间节点。一个指针每次移动 2 步快指针另外一个指针每次移动 1 步慢指针当快的指针走到终点的时候慢的指针正好位于中间节点。其正确性来源于一个朴素的数学事实快指针速度是慢指针的 2 倍当快指针走完全程n步时慢指针恰好走了n/2步。因此慢指针停留的位置就是链表的中间位置。对于本题偶数长度返回第二个中间结点的额外要求还需要在快慢指针的基础上处理长度奇偶性具体见下文源码分析。仓库源码实现解析完整实现代码该题在仓库中的源码位于 leetcode/0876.Middle-of-the-Linked-List/876. Middle of the Linked List.go完整实现如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // ListNode define type ListNode structures.ListNode /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func middleNode(head *ListNode) *ListNode { if head nil || head.Next nil { return head } p1 : head p2 : head for p2.Next ! nil p2.Next.Next ! nil { p1 p1.Next p2 p2.Next.Next } length : 0 cur : head for cur ! nil { length cur cur.Next } if length%2 0 { return p1.Next } return p1 }代码逐段解读边界处理if head nil || head.Next nil { return head }。空链表或仅含一个结点的链表直接返回头结点题面保证非空但该判断使函数具备更强的健壮性也便于在其他题目中复用。快慢指针推进p1慢指针每次走 1 步p2快指针每次走 2 步循环条件为p2.Next ! nil p2.Next.Next ! nil确保快指针不会越界。奇偶长度判定循环结束后p1指向的是偏向左侧的中间结点即偶数长度时指向第一个中间结点。此时再遍历一次统计链表总长度若length%2 0偶数长度返回p1.Next即第二个中间结点若为奇数直接返回p1。以[1,2,3,4]为例快慢指针停止时p1指向值为 2 的结点第一个中间结点长度 4 为偶数因此返回p1.Next即值为 3 的结点——恰好满足题目返回第二个中间结点的要求。这与 README 中如果链表长度是双数输出中间结点是中位数后面的那个结点的说明完全一致。复杂度分析时间复杂度O(n)。快慢指针部分一次遍历奇偶判定部分另一次遍历总代价仍为线性空间复杂度O(1)。仅使用两个指针变量无额外存储。链表数据结构与测试工具ListNode 定义仓库将链表结点统一封装在 structures/ListNode.go 中供所有链表类题目复用// ListNode 是链接节点 // 这个不能复制到*_test.go文件中。会导致Travis失败 type ListNode struct { Val int Next *ListNode }切片与链表的互转工具同一文件中还提供了两个高频工具函数方便构造输入与验证输出Ints2List(nums []int) *ListNode将整数切片转换为单链表空切片返回nilList2Ints(head *ListNode) []int将链表还原为整数切片并内置 100 层深度限制超出时 panic 提示可能存在环状链条避免死循环。本仓库的题解实现leetcode/0876.Middle-of-the-Linked-List/876. Middle of the Linked List.go通过type ListNode structures.ListNode类型别名直接复用该结构体这也是仓库各题解保持代码风格一致的关键。测试用例与验证测试文件 leetcode/0876.Middle-of-the-Linked-List/876. Middle of the Linked List_test.go 覆盖了四组典型场景输入期望中间结点值覆盖场景[1,2,3,4,5]3奇数长度链表对应题目示例 1[1,2,3,4]3偶数长度链表返回第二个中间结点对应返回第二个中间结点规则[1]1单结点链表题面下限边界[]空空链表健壮性边界测试主体通过structures.Ints2List(p.one)构造链表、调用middleNode后以structures.List2Ints(...)转回切片输出验证完整演示了工具函数与题解的配合方式。快慢指针技巧的延伸应用README 提到这题在前面题目中反复出现了很多次了快慢指针确实是链表题中的基础且高频技巧在本仓库中可以找到多处直接印证1. 归并排序找中点148. Sort Listleetcode/0148.Sort-List/148. Sort List.go 中定义了同名的middleNode辅助函数用快慢指针找到链表中点后从中间断开再分别对左右两半递归排序、最后归并——这正是链表归并排序的标准实现middleNode : middleNode(head) cur middleNode.Next middleNode.Next nil middleNode cur left : sortList(head) right : sortList(middleNode) return mergeTwoLists(left, right)注意该处的middleNode在偶数长度时返回的是第一个中间结点无奇偶修正逻辑因为归并排序只需要将链表近似均分无需满足 876 题的第二个中间结点要求。这恰好说明相同的快慢指针骨架可根据具体场景微调返回语义。2. 环形链表检测141. Linked List Cycleleetcode/0141.Linked-List-Cycle/141. Linked List Cycle.go 使用同款双指针检测环快指针每次走 2 步、慢指针每次走 1 步若两者相遇则说明存在环fast : head slow : head for fast ! nil fast.Next ! nil { fast fast.Next.Next slow slow.Next if fast slow { // 存在环 } }此外环形链表入口定位142. Linked List Cycle II、链表中删除倒数第 N 个结点19. Remove Nth Node From End of List等题目同样依赖双指针思想。掌握 876 题的快慢指针等于掌握了这一系列题目的共同起点。小结LeetCode 876 题的核心是快慢指针快指针 2 步、慢指针 1 步快指针到终点时慢指针即中点一次遍历完成偶数长度返回第二个中间结点的要求通过一次额外长度统计 length%2判定实现仓库在 structures/ListNode.go 中统一封装了ListNode及切片互转工具使题解与测试保持简洁同样的快慢指针思想在链表归并排序148 题与环形链表检测141 题等场景中广泛复用值得作为链表基础功熟练掌握。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考