141.Linked List Cycle (Medium)

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

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

Solution 1: fast and slow pointers O(n); O(1)

1-2-3-4-5
    |   |
    8-7-6
fast:1 3 5 7 3 5 7
slow:1 2 3 4 5 6 7
difference between the 2 runners:是4，不是2，所以要跑4次才能追上

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) { //0 or 1 node
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) { //不需要考虑fast.next.next，这里是fast，不是head
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { //fast追上slow，这样写很有语义
                return true;
            }
        }
        return false;
    }

以下写法已经被舍弃

    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode fast = head;        
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) { //fast追上slow
                return true;
            }
        }
        return false;
    }