《剑指Offer》，如何找出链表中是否有环（Java版）

朱雀 2022-02-25 00:28 180阅读 0赞

> 链表中是否有环。
> 
> 求出环的长度。
> 
> 求出环的入口。

1. 绝大多数人都能够很快的想起来HashSet去存储链表中的节点，Set中如果已经存在，那么含有环。

但是一般情况下，链表的值都会很大，而且HashSet的速度也并不高效，面试官不会喜欢这个解法，很可能要求我们拿出更高效的解法。

2. 快慢双指针法。

简单举个例子，现在A和B在同一个起点向前出发，A的速度比B慢，那么如果A遇到了B，那么只有一种可能：有环(一切都正常的情况下)。

那么我们只需要用代码模仿出来这个过程即可。

先写伪代码。

// A 我们称其为慢指针。
    
    // B 我们称其为快指针。
    
    // 为了简单起见，我们让B的速度为2 * Node/s,A的速度是B的一半：1 * Node/s；
    
    
    // 开始模拟，如果 B 走到链表的末端，那么不存在环，如果存在环是没法走到末端的。
    // （循环跳出条件，因为B跑得快，A走得慢，所以如果有末端，那么一定是B先到达）
    // while(B != null){
    
    
    // 如果 A == B，A与B走到了同一个节点上，那么这就是有环，并且两指针是在环的某一不确定位置相遇的。
    // if(A == B){
    //     return true;
    // }

转化为java代码：

boolean findCircle(Node head){
    // A 我们称其为慢指针, 刚开始是站在起点。
        Node A = head;
    // B 我们称其为快指针,刚开始也是站在起点。
        Node B = last;
    // 为了简单起见，我们让B的速度为2 * Node/s,A的速度是B的一半：1 * Node/s；
    
    
    // 开始模拟，如果 B 走到链表的末端，那么不存在环，如果存在环是没法走到末端的。
    // （循环跳出条件，因为B跑得快，A走得慢，所以如果有末端，那么一定是B先到达）
    // 如果 A == B，A与B走到了同一个节点上，那么这就是有环，并且两指针是在环的某一不确定位置相遇的。
    // if(A == B){
    //     return true;
    // }
        // 开始模拟两人的运动过程
        while(B != null && B.next != null){
                B = B.next.next;
                A = A.next;
                if(A == B){
                   return true;
                }
        }
        // B 已经到达终点，说明不存在环
        return false;
    }
    
    class Node {
        int val;
        Node next;
    }

我们现在已经确定是否有环了，如果有环的话，我们怎样才能知道环的长度呢？

还是举例子吧： 长跑运动员B与林黛玉A 在操场上相遇了，现在如果知道两人的速度，怎样得知操场的长度？

最简单的办法就是：林黛玉您歇着吧，运动员你也稍微慢点，1 \* Node / s的速度就挺好,然后测出运动员下次与林黛玉相遇的时间间隔。

简单来说就是：A节点站在原地不动，B节点每步只走一个节点，然后计数B的步数，直到两者相遇。

为了写代码简单起见，我们将问题修改为：

> 如果一个链表中有环，那么返回环的长度，如果没有，返回-1；

boolean getCircleLen(Node head){
        // 重复注释不再赘述
        Node A = head;
        Node B = last;
        // 开始模拟两人的运动过程
        while(B != null && B.next != null){
                B = B.next.next;
                A = A.next;
                if(A == B){
                    // 此时让B开始每步一个节点，A站在原地
                    int len = 1;
                    B = B.next;
                    while(A != B){
                        B = B.next;
                        len++;
                    }
                    return len;
                }
        }
        // B 已经到达终点，说明不存在环
        return -1;
    }
    
    class Node {
        int val;
        Node next;
    }

我们现在知道了环的长度，这一步对于第三问的重要性非常之大。

假设宿舍到操场的距离为x, 操场的长度已知为len，那么从宿舍到操场走一圈的路程为  x + len，我们让一个人先走 len步，然后两个人同时走x 步后一定会在操场入口相遇，先走的人走了x + len 步，后走的人走了x步。

我们让林黛玉A先走len步，然后运动员从宿舍出发，运动员和林黛玉以相同的步子前进，那么当运动员走到林黛玉身边的时候，记录此时林黛玉的步数，那么就求出了x 的长度.

先写伪代码:

// 先通过上一步过程计算出圈的长度 len。
    
    // 前指针 A 先走 len 步
    
    // 后指针指向头节点。
    
    // 前后双指针同步向前走，当A 与 B 相遇时，此时为环的入口.

Node getCircleHead(Node head){
        // 先通过上一步过程计算出圈的长度 len。
        Node A = head;
        // 前指针 A 先走 len 步
        int len = getCircleLen(head);
        while(len-- != 0){
            A = A.next;
        }
        // 后指针指向头节点。
        Node B = head;
        // 前后双指针同步向前走，当A 与 B 相遇时，此时为环的入口.
        while(A != B){
            A = A.next;
            B = B.next;
        }
        return B;
    }