leetcode || 141、Linked List Cycle

problem：

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

Follow up:

Can you solve it without using extra space?

Hide Tags   Linked List Two Pointers

thinking：

（1）如果可以開設額外的空間，使用unordered_set存儲周遊過的結點，出現重複時即為存在環形結構

（2）如果不适用額外的空間，及空間複雜度為O（1），這裡使用快、慢雙指針。慢指針每次走一步，快指針每次走兩步。

如果存在環形結構，兩個指針總會相遇。

（3）終止條件也要注意：

fast!=NULL && fast->next!=NULL
           

防止出現fast->NULL->next

code：

/**
 * 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) {
          ListNode *fast,*slow;
         if(head==NULL) return false;
         slow=head;
         fast=head->next;
         while(fast!=NULL && fast->next!=NULL)
         {
             if(slow==fast) return true;
             slow=slow->next;
             fast=fast->next->next;
         }
         return false;
    }
};