Leetcode42-环形链表

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

代码

static public ListNode hasCycle_StartNode(ListNode head) {ListNode slow = head, fast = head; // 将 fast 的起始位置设置为 headwhile (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 此时slow和fast在环的中相遇，但是相遇的点不一定是环的入口点，因为进入指针环的时机是不一样的ListNode cycle = head;// 重置一个新节点，走a的距离，就可以和slow后续的移动汇合，且一定是环开始的节点while (cycle != slow) {cycle = cycle.next;slow = slow.next;}return cycle;}}return null;
}

总结

a：从链表头到环的起始节点的距离。
b：从环的起始节点到快慢指针相遇点的距离。
c：环的长度。

慢指针 slow 从头节点开始，走了 a + b 的距离到达相遇点。
快指针 fast 从头节点开始，走了 a + b + n*c 的距离（其中 n 是快指针在环内绕的圈数）。
当快慢指针相遇时，有以下关系：

• slow 走的距离：a + b
• fast 走的距离：a + b + n*c

由于快指针的速度是慢指针的两倍，得出： 2(a + b) = a + b + nc => a + b = nc
这表明慢指针走的距离a+b是环长度的整数倍