Day7| 142. 环形链表 II

第 7 天 环形链表判定今日任务： 142. 环形链表 II 总结链表与数组的适用场景差异，提交第一周学习小结 题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。 题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/ 视频链接：https://www.bilibili.com/video/BV1if4y1d7ob

快慢指针法

使用快慢指针检测链表是否存在环。快指针每次移动两步，慢指针每次移动一步。若两指针相遇，说明存在环。

相遇后，将快指针重新指向链表头部，改为每次移动一步。快慢指针再次相遇的节点即为环的入口节点。

数学推导：设链表头到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c。根据快慢指针移动关系可得2(a + b) = a + b + n(b + c)，化简得a = (n - 1)(b + c) + c。

算法技巧

• 双指针：解决链表环检测、有序数组等问题
• 递归：树形结构问题
• 滑动窗口：子串/子数组问题
• 分治：复杂问题分解

学习收获

• 理解不同数据结构的特点和适用场景
• 掌握基础算法思想和实现方法
• 提升问题分析和解决能力
• 培养代码调试和优化习惯