[LeetCode] Linked List Cycle

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随便设置一个数就可以了。

因为我们只是检测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;    }}