环形链表II Posted on 2021-07-12 00:00:00 2021-07-12 00:00:00 by Author 摘要 给定一个链表和一个头指针，你能判断链表是否是环形吗？？？？？，如果是环形，阔以找出入环节点吗？？？ # 环形链表II 1. 题目描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 2. 示例描述： - 示例一： - 输入：head = [3,2,0,-4], pos = 1 - 输出：返回索引为 1 的链表节点 - 解释：链表中有一个环，其尾部连接到第二个节点。 - 示例二： - 输入：head = [1,2], pos = 0 - 输出：返回索引为 0 的链表节点 - 解释：链表中有一个环，其尾部连接到第一个节点。 - 示例三： - 输入：head = [1], pos = -1 - 输出：返回 null - 解释：链表中没有环。 3. 解题思路：对于这道题，需要使用的数学的知识，对于这道题我也不太会做，我是参考公众号《代码随想录》，carl哥思路，然后用我的思维来解释她的思想(详细请参考他公众的这篇文章)。首先判断链表是否有环，可以用快慢指针来判断，假如链表有环，怎么找到入环的节点尼。 首先我们知道`slow*2 == fast`(这里指的是步数，同时前提是链表有环的情况下)，假如链表的入环节点在第x位置，那么我们知道不管如何，快慢指针都会相遇，他们必定在环内相遇，我们又假设相遇的节点位置距离环入口位置为X，环内其余节点到环入口的距离为Y,那么我们就有一个公式：`(x + y)* 2 =x+y+n(y+z)`,具体解释一些这个公式：(x+y)是slow指针走的步数，`x+y+n(y+z)`是fast指针走的步数，为什么需要加上n(y+z),因为我们不知道fast指针到达在环内转了几圈，我们暂且让他转了n圈，然后fast指针与slow指针相遇，经过化简可得：`x = (n - 1) (y + z) + z` ,x即为环入口的位置。那么n取多少尼，因为有环，所以n至少取1，那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，fast指针在环里 多转了(n-1)圈，然后再遇到slow，相遇点依然是环形的入口节点。代码实现细节如下。 4. 代码实现： ```java public ListNode detectCycle(ListNode head) { //定义快慢指针，判断有环与在环内相交的地方 ListNode fast = head, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; //找到相交的地方 if (slow == fast) { //慢指针从链表头部开始 slow = head; //之后快慢指针分别移动一位，找到相交的地方即为入口节点 while (slow != fast) { fast = fast.next; slow = slow.next; } //有环，找到环入口，返回 return slow; } } //没有环,返回null return null; } ```
{{ item.content }}
{{ child.content }}