Linked List Cycle @LeetCode

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

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

	package leetcode.linkedlist;
	import java.util.Hashtable;
	/**
	* Solution:
	* 1.If has cycle in list, fast will catch up slow finally(fast == slow).
	* 2.If not, will never. Fast will go the end at first (fast.next == null || fast.next.next == null)
	*
	* Extra Space Solution:
	* Use Hashtable stores pointer, if contains same key --> cycle.(how to code in java? we can't)
	*
	* There're two kind of cycle. hashtable can handle these two.
	*
	* @author jeffwan
	* @date Feb 16, 2014
	*/
	public class HasCycle {
	public boolean hasCycle(ListNode head) {
	if (head == 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;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw HasCycle.java hosted with ❤ by GitHub