141. 环形链表

第一种双指针，一个每次走一步，一个每次走两步，如果有环，走的快的会超越慢的，然后呢再追上慢的，我们就看是否存在这种追上，如果说没有追上，那就是走的快的最先到达nullptr

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

第二种 利用哈希表

/**
* 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) return false;
       auto pt = head;
       unordered_set<ListNode*> s;
       while(s.find(pt) == s.end())
       {
           s.insert(pt);
           pt = pt->next;
           if(!pt)
               return false;
       }
       return true;
   }
};

第二次写题

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