代码随想录-环形链表II

题目与解析

题目链接:环形链表II

本题两个关键点，1、确定有环 2、确定环的入口位置

提供两种解法，第一种是我借助了一个辅助的列表来记录指针，空间复杂度O(n)比较无脑

第二种是Carl哥的双指针法，又是套圈问题，虽然很难想，但还是推荐这种方式，这才是算法

解法一:

public class Solution {public ListNode detectCycle(ListNode head) {//方法一、O(n)的辅助空间。记录的一定不能是val，一定是ListNode，搞个list记录一下它List nodeList = new ArrayList<ListNode>();ListNode curNode = head;while(curNode!=null){if(nodeList.contains(curNode)){return curNode;}nodeList.add(curNode);curNode = curNode.next;}return null;}
}

解法二:快慢指针

思路

方法二采用快慢两个指针的方式，(1)如果快慢指针相遇，则说明有环 (2)有环确定环的入口,借助数学公式推理。

先来个图标注一下环形链表的x、y、z(引用自网站代码随想录代码随想录)

假设有环，快指针相对于慢指针每次移动一个距离，所以必然会相遇，可以自己推一下
那么相遇时快慢指针相遇时走过的路程的比值是 1:2 => 2(x+y) = x+y+n(y+z) 整理得 x=n(y+z)-y = (n-1)(y+z)+z
当n=1时，说明快指针只走了一圈就与慢指针相遇 => x=z,此时让两个指针分别从head和相遇处出发，两个指针相遇刚好是入口
当n>1 时，无非是从环里出发的指针在环里多走了几圈，但是相遇位置是一样的，还是入口

代码

public class Solution {public ListNode detectCycle(ListNode head) {//方法二//方法二采用快慢两个指针的方式，(1)如果快慢指针相遇，则说明有环 (2)有环确定环的入口,借助数学公式推理//假设有环，快指针相对于慢指针每次移动一个距离，所以必然会相遇，可以自己推一下//那么相遇时快慢指针相遇时走过的路程的比值是 1:2  => 2(x+y) = x+y+n(y+z)  整理得 x=n(y+z)-y = (n-1)(y+z)+z//当n=1时，说明快指针只走了一圈就与慢指针相遇 => x=z,此时让两个指针分别从head和相遇处出发，两个指针相遇刚好是入口//当n>1 时，无非是从环里出发的指针在环里多走了几圈，但是相遇位置是一样的，还是入口处ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null){fast = fast.next.next;slow = slow.next;//相遇了，说明有环if(slow == fast){//搞两个指针 1从head出发，2从当前位置出发ListNode p1 = head;ListNode p2 = slow;while(p1!=p2){p1 = p1.next;p2 = p2.next;}return p1;}}return null;}
}