算法训练营第七天|142.环形链表Ⅱ

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/

视频链接：https://www.bilibili.com/video/BV1if4y1d7ob

题目描述：

测试用例：

算法描述：

这个算法的目标是：给定一个单链表的头节点 head，找到并返回链表的中间节点。如果链表有两个中间节点，则返回第二个。
核心思想：快慢指针
这个算法的核心思想是定义两个指针，从链表的头节点同时出发：
慢指针 (slow)：每次向后移动一个节点。
快指针 (head)：每次向后移动两个节点。
你可以想象成两个人在跑步，一个人（快指针）的速度是另一个人（慢指针）的两倍。当跑得快的人到达终点时，跑得慢的人恰好就在路程的中间位置。
代码逻辑解析
虽然你提供的代码片段不完整，但其核心部分清晰地展示了算法的执行流程：
初始化：slow 和 head（在此处充当快指针）都从链表的头节点开始。
循环移动：在一个循环中（循环条件通常是快指针 head 及其下一个节点 head.next 不为空），两个指针同时移动。

slow = slow.next; // 慢指针走一步
head = head.next.next; // 快指针走两步
返回结果：当快指针 head 到达链表末尾时，循环结束。此时，慢指针 slow 所指向的节点就是链表的中间节点。

举例说明
奇数个节点：1 -> 2 -> 3 -> 4 -> 5
初始：slow 指向 1，head 指向 1。
第一次移动后：slow 指向 2，head 指向 3。
第二次移动后：slow 指向 3，head 指向 5。
head 无法再走两步，循环结束。slow 指向的 3 就是中间节点。
偶数个节点：1 -> 2 -> 3 -> 4 -> 5 -> 6
初始：slow 指向 1，head 指向 1。
第一次移动后：slow 指向 2，head 指向 3。
第二次移动后：slow 指向 3，head 指向 5。
第三次移动后：slow 指向 4，head 指向 null (越过了 6)。
循环结束。slow 指向的 4 就是第二个中间节点。
这种算法非常高效，只需要遍历一次链表。

时间复杂度为 O(n)；

空间复杂度为 O(1)；