经典环形链表的思路和结论_环形链表 思路数学论证

以题引理

题·一

• 题目链接：环形链表
  

思路·快慢指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        struct ListNode* slow,*fast=head;
        while(fast && fast->next) {
            slow=slow->next;
            fast=fast->next->next;
            if(slow ==fast) {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提升·延申

证明·1

1. 条件：slow指针和fast指针同时从链表的开始位置出发，slow每次走一步，fast每次走两步。为什么slow和fast一定会在环中相遇？会不会在环里面错过，永远遇不上？请证明一下结论
   • 结论：他们一定会相遇。

证明·2

2. 为什么slow走一步，fast走的两步呢？能不能fast走一次走n步（n>2）？请证明一下结论
   • 结论：fast一次走n步？n>2不一定会相遇。
     
     
     
     

题目·二

• 题目链接

结论·入口相遇定理【自己瞎起的】

• 让一个指针从列表起始位置开始遍历链表。同时让一个指针从判环相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

证明·结论