/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

    //
    public ListNode detectCycle(ListNode head) {


		Set set = new HashSet();
		while (head != null) {
			if (set.contains(head))
				break;
			set.add(head);
			head = head.next;
		}
		return head;


    }

    public ListNode detectCycle2( ListNode head ) {
	   if( head == null || head.next == null ){
	   	return null;
	   }

	   //1
       ListNode fp = head, sp = head;
       while( fp != null && fp.next != null){
       	sp = sp.next;
       	fp = fp.next.next;
       	if( fp == sp ){
       		break;
       	}
       }

	   //2
       if( fp == null || fp.next == null ){
       	return null;
       }

	   //3slowheadfast
       sp = head;
       while( fp != sp ){
       	sp = sp.next;
       	fp = fp.next;
       }
       return sp;
    }
}