学步园

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

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

思路：

参见Elements of Programming，其中讨论orbit的时候提到了这个问题的方法。也就是选择两个指针，一个指针跑得比另外一个指针快。如果跑得快的指针遇到了终点，那么就不存在环，否则，如果两个指针相遇，就说明存在环。

题解：

/**
 * 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 == nullptr)
            return false;
        
        ListNode* fwd = head;
        ListNode* fwd2 = head -> next;
        while(fwd2 != nullptr)
        {
            if (fwd2 == fwd)
                return true;
                
            fwd2 = fwd2->next;
            if (fwd2 != nullptr)
                fwd2 = fwd2->next;
            fwd = fwd->next;
        }
        
        return false;
    }
};