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

Follow up:

Can you solve it without using extra space?

 

这道题很简单也很经典感觉。一开始用hashset做的，但这样就用了extra space了。后来发现可以用双指针。

hashset

public class Solution {    public boolean hasCycle(ListNode head) {        if (head == null) {            return false;        }        Set
      
        hs = new HashSet<>();        while (true) {            if (head == null) {                return false;            }            if (hs.contains(head)) {                break;            }            hs.add(head);            head = head.next;        }        return true;    }}
      

双指针

public class Solution {    public boolean hasCycle(ListNode head) {        if (head == null) {            return false;        }        ListNode fast = head;        ListNode slow = head;        while (fast.next != null) {            fast = fast.next.next;            slow = slow.next;            if (fast == slow) {                return true;            }            if (fast == null) {                break;            }        }        return false;    }}

双指针是公认的解法，这次都忘记了，下次要记住。。。