Given a linked list, determine if it has a cycle in it.
Follow up: Can you solve it without using extra space?
最常见的想法是遍历linked list，同时用个set进行记录遍历过的节点，如果遍历linked list时发现当前节点已经在set中出现过了。那就说明成环了。set将使用O(N)的空间复杂度。这就是我最开始选择的方法。
public boolean hasCycle(ListNode head) { if (head == null || head.next == null) return false; Set<ListNode> set = new HashSet<ListNode>(); set.add(head); ListNode p = head.next; while (p != null) { if (set.contains(p)) { return true; } else { set.add(p); } p = p.next; } return false; }但是，题目要求不用extra space。所以可以考虑两个指针first, second在linked list上遍历，一个跑得快，一个跑得慢。如果linked list成环，那么慢指针终将被快指针追上。一个跑得快，一个慢，如果有环，快的肯定会追上慢的。
public Boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode fast, slow; fast = head.next; slow = head; while (fast != slow) { if(fast==null || fast.next==null) return false; fast = fast.next.next; slow = slow.next; } return true; }这个思想还是比较重要。理解理解理解。
LeetCode官方讨论区
