环形链表II（快慢指针）

题目：https://leetcode-cn.com/problems/linked-list-cycle-ii/ 题解：假设该表是环形链表，链式部分长度为 a a a，环形部分长度为 b b b。定义快指针 f a s t fast fast和慢指针 s l o w slow slow，先让 f a s t fast fast每次走两步， s l o w slow slow每次走一步，直到两者相遇；接着让 f a s t fast fast重置回头结点， f a s t fast fast和 s l o w slow slow都每次走一步，可以证明 f a s t fast fast走 a a a步后刚好和 s l o w slow slow相遇。 假设第一次 s l o w slow slow走了 ( a + k ) (a+k) (a+k)步，那么 f a s t fast fast走了 ( a ∗ 2 + k ∗ 2 ) (a*2+k*2) (a∗2+k∗2)步，且有 ( a + 2 ∗ k ) % b = = k % b (a+2*k)\%b==k\%b (a+2∗k)%b==k%b；接着 f a s t fast fast从头开始，走 a a a步后，刚进入环形圈，要证明 s l o w slow slow也刚好走到环形圈起点，即证 ( a + k ) % b = = 0 (a+k)\%b==0 (a+k)%b==0。在式子 ( a + 2 ∗ k ) % b = = k % b (a+2*k)\%b==k\%b (a+2∗k)%b==k%b两边减去 k k k，得证。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        /*
        *给定一个链表，返回链表开始入环的第一个节点。 
        *如果链表无环，则返回 null
        */
        ListNode *fast = head;
        ListNode *slow = head;
        if(head == nullptr) return nullptr;
        do{
            if(fast->next == nullptr || fast->next->next == nullptr)
                return nullptr;
            fast = fast->next->next;
            slow = slow->next;
        }while(fast != slow);
        fast = head;
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};