给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
// 输入：head = [3,2,0,-4], pos = 1输出：// 返回索引为 1 的链表节点// 解释：链表中有一个环，其尾部连接到第二个节点。
理解题意
注意：不允许修改链表，所以不能够在节点中做标记。
遍历这个链表，如果存在环，那么输出环的开始节点，否则输出null。
数据结构及算法思维的选择
基本解法及编码的实现
暴力解法：
var detectCycle = function(head) {if (!head) return null;const hash = new Map();while(head.next !== null) {if (hash.get(head)) {return head}hash.set(head, 1);head = head.next;}return null};
时间复杂度：O(n)
- 需要遍历整条链表 O(n)
空间复杂度：O(n)
保存已遍历链表的节点，虽然最大节点数为10000个，但是我认为还是为n
思考最优解
剔除无效代码或优化空间消耗
- 需要定义一个map数据结构来保存已经遍历的节点
寻找更好的算法思维
-
最优解思路及编码实现
使用快指针追上慢指针，证明形成闭环。此时设链表头节点到链表环开始节点长度为A，当前快指针匹配到慢指针的位置为B（距离链表环节点到匹配到的节点距离为B），剩余长度为C（匹配到节点的位置到环开始节点距离），A + B为当前慢指针遍历过的的长度，A + (B + C)N + B 为快指针走的长度 N代表快指针在环中走的圈数，存在 2(A + B) = A + B + N(B + C); A = N(B + C) - B = (N - 1)(B + C) + C; C(此时如果从匹配到节点的位置到环开始节点位置)+ (N - 1) 环长度进行遍历，新节点从链表开始节点开始遍历，此时当(N - 1) 环长度遍历完成后，也就是新节点此时刚好到链表环节点开始节点位置，停止遍历，返回正确的值。
* 最优解：
边界细节问题和复杂度分析function detectCycle(head: ListNode | null): ListNode | null { if (!head) return null; let slow = head, fast = head; while (fast) { slow = slow.next; // 如果快指针结束 证明不形成闭环 if (fast.next) { fast = fast.next.next; } else { return null; } // 确定当前链表有环 if (fast === slow) { // 设链表头节点到链表环节点长度为A // 当前快指针匹配到慢指针的位置为B // 剩余长度为C // A + B为当前慢指针的长度 // A + (B + C)N + B 为快指针走的长度 N代表快指针在环中走的圈数 // 存在 2(A + B) = A + B + N(B + C); A = N(B + C) - B = (N - 1)(B + C) + C; let newListNode = head; // A长度遍历完之时 就是 匹配到答案之时 while (slow !== newListNode) { slow = slow.next; newListNode = newListNode.next; }; return newListNode; } } return null; };时间复杂度：O(n)
-
遍历链表
空间复杂度: O(1)
若有收获，就点个赞吧
0 人点赞
