141. Linked List Cycle

5/1/2028 update:
The solution below is the best so far.
Because fast.next and fast.next.next have been used within the while loop. So the condition of while loop is fast != null and fast.next != null. If we call fast.next when fast == null, there will be null pointer issue.

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

--------------------------------------------------------------------------------------------------------------------------
思路：
一快一慢两个node, 快的走两步，慢的走一步。如果快的和慢的重合，那么这个linkedlist就有cycle。

实现：
先要检查head 和head.next是否为空。然后slow指向head, fast指向head.next。循环条件是fast != slow。在循环里面fast 和slow往下走。如果fast == null  或者fast.next == null则没有cycle。这里检查fast.next是否为空很重要，后面fast 往下走2不，如果fast.next为空则会报错。代码如下：

 public class Solution {  
   /*  
    * @param head: The first node of linked list.  
    * @return: True if it has a cycle, or false  
    */  
   public boolean hasCycle(ListNode head) {  
     // write your code here  
     if( head == null || head.next == null)  
       return false;  
     ListNode slow = head;  
     ListNode fast = head.next;  
     while(fast != slow) {  
       if(fast == null || fast.next == null) {  
         return false;  
       }  
       fast = fast.next.next;  
       slow = slow.next;  
     }  
     return true;  
   }  
 }