【LeetCode】141 Linked List Cycle （java實作）

Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

題目很明确，給定一個連結清單，判斷其中是否包含一個環路。有個額外的要求就是不使用額外的空間。

假如說沒有這個額外的要求，有什麼方法可以解決呢？建立一個哈希表，周遊連結清單中的每個元素，并将其假如哈希表中，加入哈希表之前判斷是否已經存在于哈希表中，如果存在，則說明存在環，否則就是不存在環。但是，這個哈希表卻占用了O(n)的空間，是以該思路不符合要求。

這裡，我們可以使用快慢引用的思路。兩個引用都指向連結清單頭，從連結清單頭開始周遊，慢引用每次前進一步，而快引用每次前進兩步，如果連結清單是有環路的，那麼快引用終将追上慢引用；如果沒有環路，那麼周遊就會有結束的時候。代碼如下：

public
    
   class
    Solution {
    
   public
    
   boolean
    hasCycle(ListNode head) {
        
   if
    (head 
   ==
    
   null
   ) 
   return
    
   false
   ;
        
        ListNode slow 
   =
    head, fast 
   =
    head;
        
   while
    (fast.next 
   !=
    
   null
    
   &&
    fast.next.next 
   !=
    
   null
   ) {
            slow 
   =
    slow.next;
            fast 
   =
    fast.next.next;
            
   if
    (slow 
   ==
    fast) 
   return
    
   true
   ;
        }        
        
   return
    
   false
   ;
    }
}