@@ -0,0 +1,1474 @@
+Question: %0A%0AGiven a linked list, determine if it has a cycle in it.%0A%0AFollow up:%0ACan you solve it without using extra space?%0A%0AA straight forward solution would be iterating the list and using a HashSet to store unique nodes. When we encounter a node which is already in the set, it means this list has a cycle. %0ASuppose there are n nodes in the list, the time complexity is O(n), the space complexity is O(n).%0A%0Apublic class Solution %7B%0A%09public boolean hasCycle(ListNode head) %7B%0A%09%09HashSet%3CListNode%3E set = new HashSet%3CListNode%3E();%0A%09%09while (head != null)%7B%0A%09%09%09if (set.contains(head))%0A%09%09%09%09return true;%0A%09%09%09set.add(head);%0A%09%09%09head = head.next;%0A%09%09%7D%0A%09%09return false;%0A%09%7D%0A%7D%0A%0AAnother solution is to use two pointers. One of them moves one step each time. The other moves two steps each time. Eventually they will reach the same node. This could be demonstrated by going through several examples. If there is indeed a cycle, the fast pointer will always be one loop faster than the slow pointer. So the time complexity is O(n), the space complexity is O(1).%0A%0Apublic class Solution %7B%0A    public boolean hasCycle(ListNode head) %7B%0A        ListNode fast = head;%0A        ListNode slow = head;%0A        %0A        if (head != null && head.next == head) return true;%0A        %0A        while(fast != null && fast.next != null)%7B%0A            slow = slow.next;%0A            fast = fast.next.next;%0A %0A            if(slow == fast)%0A                return true;%0A        %7D%0A %0A        return false;        %0A    %7D%0A%7D%0A

add a sample question.