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

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

關于cycle，第一個想法自然就是用hashmap來做。注意用hashmap.put()method的時候，value隨便設置一個數(shù)就可以了。

因為我們只是檢測key是否有重復的，value在這里的意義不大。

代碼如下。~

/** * 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) {        HashMap<ListNode,Integer> hash=new HashMap<ListNode,Integer>();        if(head==null){            return false;        }        while(head!=null){            if(hash.containsKey(head)){                return true;            }            hash.put(head,1);            head=head.next;        }        return false;    }}

但是再看一下follow up那里要求的是without extra space，那么這樣的話hashmap就暫時不能用了。

用two pointer來做就可以了。快慢指針。（fase/slow) (fast每次走兩步，slow則是一步。）

如果有cycle的話，快慢指針一定會相遇。

/** * 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) {        if(head==null||head.next==null){            return false;        }        ListNode fast=head;        ListNode slow=head;        while(fast!=null&&fast.next!=null){            slow=slow.next;            fast=fast.next.next;            if(slow==fast){                return true;            }        }        return false;    }}