Linked List Cycle leetcode

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

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

用双指针法， 如果faster 和slower最后遇到了则有环

时间O(n) 空间O(1)

对于是否相遇的参考：转自http://www.cnblogs.com/springfor/p/3862102.html

假设Faster确实把Slower超了而且他俩还没相遇（类似Faster一下迈了2步，Slower一下迈了一步，Faster超了Slower，但是俩人并没遇上）。那么就假设Faster现在在 i+1 位置而Slower在 i 位置。那么前一时刻，Slower肯定是在 i-1 位置，而Faster肯定在(i+1)-2位置，所以前一时刻，俩人都在 i-1 位置，相遇了。

还有一种情况就是Faster在i+2位置而slower在i位置，那么前一时刻，Faster在i位置，而Slower在 i-1位置。这样问题又回归到上面那种情况了（再往前一时刻，Faster在i-2位置，Slower在i-1-1位置，相遇）。

所以，这就证明Runner和Faster在有环的链表中肯定会相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode faster = head, slower = head;
        while (faster.next != null && faster.next.next != null){
            faster = faster.next.next;
            slower = slower.next;
            if (faster == slower){
                return true;
            }
        }
        return false;
    }
}