[LeetCode]Linked List Cycle

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

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

这道题是要求在不额外使用存储空间的基础上判断一个单链表中是否存在一个环。

环的存在，就是在无环的基础上，将最后一个结点的next不设为NULL，而是指向该结点前的任意一个结点，所以包含环的单链表就没有“最后一个结点”的说法了。

思路很容易想到，设两个指针，slow 与 fast。
1. 两个指针移动的速度不同，后者是前者的两倍。
2. 若链表无环，则fast最后一定为NULL
3. 若链表有环，则 slow 与 fast一定会有指向同一个结点的时刻。

下面贴上代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
   bool hasCycle(ListNode *head) {
        if (head){
            ListNode* slow = head;
            ListNode* fast = head->next;
            while (fast&&fast->next){
                if (slow == fast)
                    return true;
                else{
                    slow = slow->next;
                    fast = fast->next->next;
                }
            }
            return false;
        }
        return false;
    }
};