Linked List Cycle

Problem:

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

Follow up:
Can you solve it without using extra space?

Analysis:

Usess Floyd’s cycle finding algorithm. Two pointer, one is the slow pointer travels a node at once the other is the fast pointer travels two nodes at once. These pointers will eventually meet at a point if the linked list has a cycle in it. The time is O(N) and space is O(1).

When coding, have to make sure the fast.next is not null otherwise a nullpointerexception will rise during execution. 

Solution:

 /**  
  * Definition for singly-linked list.  
  * class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public boolean hasCycle(ListNode head) {  
     ListNode slow=head;  
     ListNode fast=head;  
     while(fast!=null&&slow!=null&&fast.next!=null)  
     {  
       slow=slow.next;  
       fast=fast.next.next;//fast is twice as fast as slow  
       if(fast==slow)//when fast meets slow  
        return true;  
     }  
     return false;  
   }  
 }