链表--环形链表--龟兔赛跑算法

本题以及下题，实际是 Floyd's Tortoise and Hare Algorithm （Floyd 龟兔赛跑算法）

龟兔赛跑动画来自于 Floyd's Hare and Tortoise Algorithm Demo - One Step! Code (onestepcode.com)

同时在本章也提供了动态资料。

如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段：

阶段1

• 龟一次走一步，兔子一次走两步

• 当兔子能走到终点时，不存在环

• 当兔子能追上龟时，可以判断存在环

阶段2

• 从它们第一次相遇开始，龟回到起点，兔子保持原位不变

• 龟和兔子一次都走一步

• 当再次相遇时，地点就是环的入口

为什么呢？

• 设起点到入口走 a 步（本例是 7），绕环一圈长度为 b（本例是 5），

• 那么从起点开始，走 a + 绕环 n 圈，都能找到环入口

• 第一次相遇时

  • 兔走了 a + 绕环 n 圈（本例 2 圈） + k，k 是它们相遇距环入口位置（本例 3，不重要）

  • 龟走了 a + 绕环 n 圈（本例 0 圈） + k，当然它绕的圈数比兔少

  • 兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 绕环 n 圈

• 而前面分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，再走 a 步，就是环入口

阶段1 参考代码（判断是否有环）

//判断是否有环
    public boolean hasCycle(ListNode head){
        ListNode h=head; //兔
        ListNode t=head;//龟
        //判断条件：h!=null:当兔子能走到终点时，不存在环
        //h.next!=null 防止兔子连续跳两次中第一次跳出现空指针
        while(h!=null && h.next!=null){
            t=t.next;
            h=h.next.next;
            //当兔子能追上龟时，可以判断存在环
            if(h==t){
                return true;
            }
        }
        return false;
    }

测试用例：

public static void main(String[] args) {
    // 构造一个带环链表
    ListNode n12 = new ListNode(12, null);
    ListNode n11 = new ListNode(11, n12);
    ListNode n10 = new ListNode(10, n11);
    ListNode n9 = new ListNode(9, n10);
    ListNode n8 = new ListNode(8, n9);
    ListNode n7 = new ListNode(7, n8);
    ListNode n6 = new ListNode(6, n7);
    ListNode n5 = new ListNode(5, n6);
    ListNode n4 = new ListNode(4, n5);
    ListNode n3 = new ListNode(3, n4);
    ListNode n2 = new ListNode(2, n3);
    ListNode n1 = new ListNode(1, n2);
 
    n12.next = n1;
}

阶段2 参考代码（找到环入口）

 //查出环的入口
    public ListNode detectCycle(ListNode head){
        ListNode h=head; //兔
        ListNode t=head;//龟
        //判断条件：h!=null:当兔子能走到终点时，不存在环
        //h.next!=null 防止兔子连续跳两次中第一次跳出现空指针
        while(h!=null && h.next!=null){
            t=t.next;
            h=h.next.next;
            //当兔子能追上龟时，可以判断存在环
            if(h==t){
                //当符合第一阶段时，就进行第二阶段
                //2.1龟回到起点，兔子保特原位不变
                t=head;
                while(true){
                    //把if条件提到while循环最前面，是为了判断一种特殊情况：当这个环是首尾相连的大环时,
                    //龟回到起点，兔子保特原位不变 这个时候就是它们再次相遇
                    if(t==h){
                        return h;
                    }
                    //龟和兔子一次都走一步
                    t=t.next;
                    h=h.next;
                }
            }
        }
        return null;
    }

• 还有一道扩展题目，也可以用判环算法思想来解：就是力扣 287 题，寻找重复数

测试用例：

public static void main(String[] args) {
    // 构造一个带环链表
    ListNode n12 = new ListNode(12, null);
    ListNode n11 = new ListNode(11, n12);
    ListNode n10 = new ListNode(10, n11);
    ListNode n9 = new ListNode(9, n10);
    ListNode n8 = new ListNode(8, n9);
    ListNode n7 = new ListNode(7, n8);
    ListNode n6 = new ListNode(6, n7);
    ListNode n5 = new ListNode(5, n6);
    ListNode n4 = new ListNode(4, n5);
    ListNode n3 = new ListNode(3, n4);
    ListNode n2 = new ListNode(2, n3);
    ListNode n1 = new ListNode(1, n2);
 
    //n12.next = n1;
    ListNode x = new E10LetCode141().detectCycle(n1);
    System.out.println(x.value);
}