题目
题目来源leetcode
leetcode地址：142. 环形链表 II，难度：中等。
题目描述(摘自leetcode)：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 进阶： 你是否可以使用 O(1) 空间解决此题？ 示例1： 输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。 示例2： 输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。 示例3： 输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。 提示： 链表中节点的数目范围在范围 [0, 104] 内 -105 <= Node.val <= 105 pos 的值为 -1 或者链表中的一个有效索引
本地调试代码：
class Solution { public ListNode detectCycle(ListNode head) { ... } public static void main(String[] args) { //链表A ListNode aNode5 = new ListNode(5, null); ListNode aNode4 = new ListNode(4, aNode5); ListNode aNode3 = new ListNode(3, aNode4); ListNode aNode2 = new ListNode(2, aNode3); aNode5.next = aNode2;//设置入环节点 ListNode aNode1 = new ListNode(1, aNode2); //调用方法 ListNode node = new Solution().detectCycle(aNode1); System.out.println("入环节点值为："+node.val); } }
题解
NO1：快慢指针
核心问题(2点)
1、为什么慢指针一定会与快指针重合相遇？
快指针每次移动2步，慢指针移动1步，慢指针与快指针必会重合。不同情况的环快指针可能会走n圈，慢指针不会超过一圈。也就是说一圈内必重合。
2、求解到相遇的节点之后，如何确定指定的入环节点？
这里我觉得 代码随想录—题解中的图特别好这里引用一下：
慢指针走的步数：x+y
快指针走的步数：x+y+n(z+y)，这里z+y指的是环形一圈的意思，n指的是转了n圈。
因为快指针每次走两步，慢指针走一步，公式：2(x+y) = x+y+n(z+y) => x+y = n(z+y) => x = n(z+y)-y
最终化解为：x = (n-1)(z+y)+z，(n-1)(z+y)就是指的快指针环形绕的n圈意思
此时我们可以得出一个结论，当快慢指针相遇时，x与z的值都是相等的，那么我们代码中只需要求得快慢指针重合的节点以及头节点每次移动一步进行对比即可找出环形入口节点。
注：主要是看了代码随想录—题解思路再进行自己归纳总结了下。
思路及代码
思路：快慢指针(慢一步，快两步)，找到环内重合点，接着令头节点与重合节点一起移动，每次移动一步，一旦两个指针指向的节点相同就找到入环节点。
代码：
public ListNode detectCycle(ListNode head) { //节点为null、1个节点直接返回null if(head == null || head.next == null){ return null; } //快慢指针同时从头节点出发 ListNode slow = head; ListNode fast = head; //这里直接将快指针指向节点及下个节点不为空作为条件 while(fast != null && fast.next != null){ slow = slow.next;//慢指针移动一步 fast = fast.next.next;//快指针移动两步 //若是快慢指针相遇 if(slow == fast){ //两个指针一个指向头节点，另一个指针指向快节点 ListNode index1 = head; ListNode index2 = fast; //结合之前等式，我们来进行同时移动两个指针每次移动一步，一旦相等就说明找到了入环节点 while(index1 != index2){ index1 = index1.next; index2 = index2.next; } return index1;//此时返回任意一个节点即可，因为此时是index1与index2都是相同节点 } } return null; }
