從有環連結清單中如何獲得環的長度

節點類

@Data
public class Node {
    /**
     * 用于儲存節點中的資料
     */
    private Object data;
    /**
     * 用于儲存下一個節點的位址值
     */
    private Node next;

    public Node(Object data) {
        this.data = data;
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}      

實作類

package day04;

/**
 * @Author yqq
 * @Date 2022/05/09 09:46
 * @Version 1.0
 * 從有環連結清單中，獲得環的長度
 */
public class Test06 {
    public static void main(String[] args) {
        //建立一個單連結清單
        Node lastNode = new Node(55);
        Node node4 = new Node(44,lastNode);
        Node node3 = new Node(33,node4);
        Node node2 = new Node(22,node3);
        Node headNode = new Node(11,node2);
        lastNode.setNext(node2);
        int len = getLen(headNode);
        System.out.println(len);
    }

    /**
     * 獲得快慢指針相交的節點
     * @param headNode
     * @return
     */
    public static Node meetNode(Node headNode){
        //處理headNode為null的情況
        if (headNode == null)
            return null;
        //定義一個快指針，指向headNode，每次向後移動兩次
        Node fast = headNode;
        //定義一個慢指針，指向headNode，每次往後移動一次
        Node slow = headNode;
        //定義一個循環用于單連結清單是否有環
        while (fast != null && fast.getNext() != null){
            //設定快指針和慢指針每次向後移動
            fast = fast.getNext().getNext();
            slow = slow.getNext();
            //如果fast和slow指向同一個節點，則表示單連結清單有環
            if (fast == slow)
                return fast;
        }
        return null;
    }

    /**
     * 獲得有環連結清單環的長度
     * @param headNode
     * @return
     */
    public static int getLen(Node headNode){
        //獲得快慢指針相交的節點
        Node meetNode = meetNode(headNode);
        //處理meetNode為null的情況
        if (meetNode == null)
            return 0;
        //定義一個變量儲存環中節點的個數
        int size = 0;
        //從meetNode節點開始，周遊環中節點
        //定義一個臨時節點，用于輔助周遊單連結清單
        Node tempNode = meetNode;
        //定義死一個循環，用于周遊環中的節點
        while (true){
            //讓tempNode指向它的下一個節點
            tempNode = tempNode.getNext();
            //更新size的值
            size++;
            //如果tempNode和meetNode指向同一個節點，就停止周遊操作
            if (tempNode == meetNode)
                break;
        }
        //傳回環中節點的個數
        return size;
    }
}