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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
  public:
  //采用快慢指针：
  //假设：起点到环入口点的距离是a,环入口点到快慢指针相遇点的距离是b,相遇点到环入口点的距离是c
  //相遇时，快指针走a+b+m(b+c) 慢指针走a+b+n(b+c)
  //满足2[a+b+m(b+c)]=a+b+n(b+c) 化简得到a+b=(n-2m)(b+c) 即a+b=k(b+c) 
  //可以得到a=(k-1)(b+c)+c 即a=nL+c
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr ||
                head->next->next == nullptr) return false;
        ListNode* fast = head;
        ListNode* slow = head;
	  //让快慢指针相遇
        do {
            fast = fast->next;
            if (fast) {
                fast = fast->next;
            } else {
                return false;
            }
            slow = slow->next;
        } while (fast && slow && fast != slow);
        if (fast == nullptr || slow == nullptr) return false;
	  //让慢指针回到起点，满足a=nL+c，快慢指针同时走到环入口点
        slow = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        if (fast == slow) return true;
        else return false;
    }
};