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

快慢指针法判断链表中是否有环，且能够找到环的起始结点：

/**
 * 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;
        ListNode* pfast = head, * pslow = head;//快指针和慢指针
        do {
            pslow = pslow->next;
            if (pfast->next)pfast = pfast->next->next;
            else pfast = nullptr;
        } while (pfast && pfast != pslow);
        return pfast != nullptr;
        //第一次追上时, f=2s, f-s = nL(L是环的长度)，则s=nL 
        //假设环前长度为prelen，(n一定是 满足 nL>= prelen的最小数)
        //然后让快指针从头开始走,速度变为一次一步，
        //则再次相遇时:f = prelen,s = prelen+nL; 他们都只用走prelen步即可
    }
};