题解 | #判断链表中是否有环#

/**
 * 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 = head; //快步指针，一次滑动两步
        ListNode* slow = head; //慢步指针，一次滑动一步
        while (fast != nullptr && fast->next != nullptr) {
                fast = fast->next->next;
                slow = slow->next;
                if (fast == slow) //如果有环，那么快指针和慢指针最终会指向同一个结点
                    return true;
        }
        return false; 
    }
};