【算法】連結清單判斷是否有環

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        this.val = x;
        next = null;
    }
}
           

思路一：用哈希表存儲周遊所有節點

面試精簡回答

每個通路的節點，放入哈希表中，如果下一個節點已經存在于哈希表中，表示有環

時間和空間複雜度都是O(N)

//hash
    public boolean hasCycleWithHash(ListNode head){
        Set<ListNode> listNodeSet = new HashSet<>();
        while (head != null){
            if(!listNodeSet.add(head)){
               return true;
            }
            else {
                head = head.next;
            }
        }
        return false;
    }
           

思路二：快慢指針

面試精簡回答

同時出發，如果有環，跑的快的指針一定會和慢指針再次相遇

時間複雜度O(N)，空間複雜度O(1)

//do while
    public boolean hasCycleWithFastSlow(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        do {

            //判斷前面的兔子有沒有走到頭，走到頭，跳出循環
            if (fast == null || fast.next == null) {
                return false;
            }
            //自身移動
            slow = slow.next;
            fast = fast.next.next;
        } while (fast != slow);

        return true;
    }
           

換while結構，初始化slow和fast的差别

//while
    public boolean hasCycleMethod(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
//判斷
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }