判斷鏈表中是否有環

先來看一張圖：

 

我們能夠清楚的看到，在這個單鏈表中，是有環的。那么使用代碼，該如何判斷它是否有環呢？

先別著急看代碼，先和阿粉一起來分析一下，有了思路，代碼實現相對就比較容易。

判斷鏈表中是否有環，可以從頭結點開始，依次遍歷單鏈表中的每一個節點。每遍歷一個節點，就和前面的所有節點作比較，如果發現新節點和之前的某個節點相同，則說明此節點被遍歷過兩次，說明鏈表有環，反之就是沒有。

但是仔細看一下這種方法，你會發現這種方法很耗時耗力，因為每遍歷一個節點，都要把它和前面所有的節點都比較一遍。別著急，阿粉還有一個很巧妙的方法，就是使用兩個指針。這樣思路就可以這樣想：

使用兩個指針，一個快指針，一個慢指針。快指針每次走 2 步，慢指針每次走 1 步。如果鏈表中沒有環，則快指針會先指向 null 如果鏈表中有環，則快慢指針一定會相遇。

思路打通，咱們就可以使用代碼來進行實現了：

/**
 * 判斷鏈表是否有環
 */
public class IsHasLoop {
    public static class Node{
        private int data;
        private Node next;
        public Node(int data,Node next){
            this.data=data;
            this.next=next;
        }
        public int getData(){
            return data;
        }
    }
    public static void main(String[] args){
        // 初始化單鏈表
        Node node5=new Node(5,null);
        Node node4=new Node(4,node5);
        Node node3=new Node(3,node4);
        Node node2=new Node(2,node3);
        Node node1=new Node(1,node2);
        // 讓 node5 的指針指向 node1 形成一個環
        node5.next=node1;

        boolean flag=isHasLoop(node1);
        System.out.println(flag);

    }
    public static boolean isHasLoop(Node list){
        if (list == null){
            return false;
        }

        Node slow=list;
        Node fast=list;

        while (fast.next != null && fast.next.next != null){
            // 慢指針走一步,快指針走兩步
            slow=slow.next;
            fast=fast.next.next;
            // 如果快慢指針相遇,則說明鏈表中有環
            if (slow==fast){
                return true;
            }
        }
// 反之鏈表中沒有環
        return false;
    }
}

求環長

現在判斷鏈表中是否有環這個問題已經解決了，阿粉覺得不能到此為止，思路就向外擴散了一下，既然有環了，如果想要求環長該怎么辦呢？

既然快慢指針相遇了，阿粉記錄下此時的位置，接下來再讓滿指針繼續向前走，每次走 1 步，這樣當慢指針再次走到相遇時的位置時，慢指針走過的長度不就是環長嘛

public static int getLength(Node list){
        // 定義環長初始值為 0
        int loopLength=0;
        Node slow=list;
        Node fast=list;

        while (fast != null && fast.next != null) {
            // 慢指針走一步,快指針走兩步
            slow=slow.next;
            fast=fast.next.next;

            // 第一次相遇時跳出循環
            if (slow == fast) break;
        }
        // 如果 fast next 指針首先指向 null 指針,說明該鏈表沒有環,則環長為 0
        if(fast.next == null || fast.next.next == null){
            return 0;
        }
        // 如果有環,使用臨時變量保存當前的鏈表
        Node temp = slow;
        // 讓慢指針一直走,直到走到原來位置
        do{
            slow = slow.next;
            loopLength++;
        } while(slow != temp);

        return loopLength;
}

求入環點

既然有環了，也求出了環長，那么入環點應該也知道了吧？阿粉對于求入環點這個問題有點兒懵，就畫了一張圖出來：

 

如上圖，我們假設：

入環點距離頭結點距離為 D 入環點與首次相遇點較短的距離為 S1 入環點與首次相遇點較長的距離為 S2 當兩個指針首次相遇時，慢指針一次只走 1 步，則它所走的距離為：D+S1 快指針每次走 2 步，多走了 n(n>=1) 圈，則它所走的距離為：D+S1+n(S1+S2) 快指針速度為慢指針的 2 倍，則：2(D+S1)=D+S1+n(S1+S2) 上面等式，整理可得：D=(n-1)(S1+S2)+S2

如果讓 (n-1)(S1+S2) 為 0 ，是不是 D 和 S2 就相等了？也就是說，當兩個指針第一次相遇時，只要把其中一個指針放回到頭結點位置，另外一個指針保持在首次相遇點，接下來兩個指針每次都向前走 1 步，接下來這兩個指針相遇時，就是要求的入環點。

有點兒像做數學題的感覺，還好阿粉的數學功底還是有那么一丟丟的。

基于上面的思路，代碼就很容易實現了：

public static Node entryNodeOfLoop(Node list){
        Node slow=list;
        Node fast=list;
        while(fast.next != null && fast.next.next != null){
            // 慢指針走一步,快指針走兩步
            slow=slow.next;
            fast=fast.next.next;

            // 第一次相遇時跳出循環
            if (slow == fast) break;
        }
        // 如果 fast next 指針首先指向 null 指針,說明該鏈表沒有環,則入環點為 null
        if (fast.next == null || fast.next.next == null){
            return  null;
        }
        // 第一次相遇之后,讓一個指針指向頭結點,另外一個指針在相遇位置
        // 兩個指針每次走 1 步,相遇為止,此時相遇節點即為入環點
        Node head=list; // 頭結點
        Node entryNode=slow;    // 相遇節點
        while (entryNode != head){
            entryNode=entryNode.next;
            head=head.next;
        }
        return entryNode;
}