Floyd判圈法

leetcode141-环形链表
其算法应用龟兔赛跑的思想，使用一个slow和fast指针初始都指向链表第一个节点，slow每次向前走一步，fast向前走两步。如果链表无环，那么fast会先走到NULL节点。如果有环，那么当slow和fast都进入环的时候，由于fast比slow走的快，fast总会追上slow。C++代码如下：
写法一:快慢指针不在同一起点

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

写法二:快慢指针在同一起点

/**
 * 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==NULL)
            return false;
        ListNode* slow=head,*fast=head;
        while(true){		//把跳出循环的逻辑写在循环体内部会简单一点
            slow=slow->next;
            fast=fast->next;
            if(fast==NULL) 
                return false;
            fast=fast->next;
            if(fast==NULL)
                return false;
            if(slow==fast)
                return true;
        }
        return false;
    
    }
};

注意要判断两次fast是否为空.