java實作判斷連結清單有環

判斷連結清單有環

使用兩個指針left和right指向起點，每次left指針向後走一步，right指針向後走兩步，上圖是兩個指針走一次後的結果。直到left和right指針再次指向同一個節點，說明該連結清單是有環連結清單。

private static boolean isCycle(Node node){
        if (node == null){
            throw new NullPointerException("連結清單node不能為空");
        }
        Node left = node;
        Node right = node;
        while (true){
            left = left.getNext();
            right = right.getNext().getNext();
            if (left == right){
                System.out.println("left.item="+left.getItem() + " , right.item="+right.getItem());
                return true;
            }
        }

    }
           

環的長度

left和right相遇之後，left和right分别依舊以1和2為步長向後走，因為直到再次相時，left走過的步數就是環的長度。

private static int cycleLength(Node node){
        if (node == null){
            throw new NullPointerException("連結清單node不能為空");
        }
        Node left = node;
        Node right = node;
        int count = 0;
        int length = 0;
        while (true){
            left = left.getNext();
            right = right.getNext().getNext();
            //相遇一次，開始記錄left的步數
            if (count == 1){
                ++length;
            }
            //第一次相遇，count記錄相遇的次數
            if (left == right && count <2){
                ++count;
            }
            //再次相遇，傳回left的步數，即環的長度
            if (count == 2){
                return length;
            }
        }
    }
           

求入環點

因為right的步長是left的2倍，是以第一次相遇時，有2（a+b）=a + 2b + c，即a = c。是以在left和right首次相遇時，将left重置到起點，步長不變，right還在相遇點，但步長改為1，left和right再次相遇時則為入環點。

private static Node entryPoint(Node node){
        if (node == null){
            throw new NullPointerException("連結清單node不能為空");
        }
        Node left = node;
        Node right = node;
        while (true){
            left = left.getNext();
            right = right.getNext().getNext();
            //首次相遇，left重置到起點
            if (left == right){
              left = node;
              break;
            }
        }

        while (true){
            left = left.getNext();
            right = right.getNext();
            //第二次相遇，傳回入環節點
            if (left == right){
                return left;
            }
        }
    }
           

Node類

public class Node {

    private Node next;
    private int item;

    public Node() {
    }

    public Node(int item) {
        this.item = item;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getItem() {
        return item;
    }

    public void setItem(int item) {
        this.item = item;
    }
}
           

測試

public static void main(String[] args) {
        Node node = new Node(0);
        Node temp = node;
        Node c = null;
        for (int i=1;i<=7;i++){
            Node n = new Node(i);
            temp.setNext(n);
            temp = n;
            if (i == 4){
                c = n;
            }
        }
        temp.setNext(c);
        System.out.println(isCycle(node)); //true
        System.out.println(cycleLength(node));   //4
        System.out.println(entryPoint(node).getItem()); //4
    }