leetcode(142) 《环形链表 II》算法的数学证明
算法链接：142. 环形链表 II
c++代码实现：
/**
* 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) {
ListNode *fast = head, *slow = head; // 定义快慢指针
do { // 找出相遇点
if (fast == nullptr || fast->next == nullptr ||
fast->next->next == nullptr) {
return nullptr;
} // 判断是否有环
fast = fast->next->next; // 快指针一次走两步
slow = slow->next; // 慢指针一次走一步
}while (fast != slow);
slow = head;
while (slow != fast) { // 再次相遇就是环的起始点
slow = slow->next;
fast = fast->next;
}
return slow;
}
};