代码随想录-环形链表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. 那么相遇时快慢指针相遇时走过的路程的比值是 1:2  => 2(x+y) = x+y+n(y+z)  整理得 x=n(y+z)-y = (n-1)(y+z)+z
3. 当n=1时，说明快指针只走了一圈就与慢指针相遇 => x=z,此时让两个指针分别从head和相遇处出发，两个指针相遇刚好是入口
4. 当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;

    }
}

总结

1. 链表问题两大法宝 ① 虚拟头结点 ②双指针(最多的就是快慢指针)
2. 链表部分最后两道题都涉及到数学归纳，多少有点难，想不出来就背背吧，再遇到类似的能做出来就行了