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

Follow up:

Can you solve it without using extra space?

 

[Thoughts]

有一种使用两个指针的方法，一个fast指针，每次移动两步；一个slow指针，每次移动一步。如果两个指针能相遇，则链表具有一个环形。

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

 

另一种方法(只是开玩笑)

public class Solution {    public boolean hasCycle(ListNode head) {        if(head == null)            return false;        int i = 0;        while(head.next != null){            i++;            if (i > 10000){                return true;            }            head = head.next;        }        return false;    }}