经典环形链表的思路和结论

ゞ浴缸里的玫瑰 2024-04-03 08:23 36阅读 0赞

#### 文章目录 ####

*  以题引理
 *   *  题·一
 *  思路·快慢指针
 *   *  提升·延申
     *   *  证明·1
         *  证明·2
 *  题目·二
 *  结论·入口相遇定理【自己瞎起的】
 *   *  证明·结论

## 以题引理 ##

### 题·一 ###

*  [题目链接：环形链表][Link 1]  
    ![在这里插入图片描述][3afb16ba7b4a46288655c048464d1dae.png]

## 思路·快慢指针 ##

![在这里插入图片描述][0a0c233b4ce5446db548a310af233f8c.png]

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 ####

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

![在这里插入图片描述][67e6e41b03414b57bfe01d36fb42d996.png]

#### 证明·2 ####

1.  为什么slow走一步，fast走的两步呢？能不能fast走一次走n步（n>2）？请证明一下结论
    
     *  结论：fast一次走n步？n>2不一定会相遇。  
        ![在这里插入图片描述][841782d8d7f341b2a4371ec93395d8bc.png]  
        ![在这里插入图片描述][1c29f0ff506e412fa47901e9f858ef2b.png]  
        ![在这里插入图片描述][027d8feba7784307a05475ba98a08d0a.png]  
        ![在这里插入图片描述][f1b32f125c094cb9ac4eff918e022291.png]

## 题目·二 ##

*  [题目链接][Link 2]

![在这里插入图片描述][fd63dfc0a01c4a2d891ef66ea2738043.png]

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

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

### 证明·结论 ###

![在这里插入图片描述][8c63c714f5b54613a8e1f18f2f60f885.png]

[Link 1]: https://leetcode.cn/problems/linked-list-cycle/
[3afb16ba7b4a46288655c048464d1dae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/44e665b4e213432aad1d42b37e2ded79.png
[0a0c233b4ce5446db548a310af233f8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/22562008e9d044f2a2425b9ea70c72f4.png
[67e6e41b03414b57bfe01d36fb42d996.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/d9150b40448c41a7801775bb38d81581.png
[841782d8d7f341b2a4371ec93395d8bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/517f932a6ffe4fc89b8345fc08bf59a9.png
[1c29f0ff506e412fa47901e9f858ef2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c9a19b6c22f4402ab899ec0a41362870.png
[027d8feba7784307a05475ba98a08d0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/32d35dc8dbca4593b55969242e586ef6.png
[f1b32f125c094cb9ac4eff918e022291.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1dfd2d6783304c37ad0ff618060f4d07.png
[Link 2]: https://leetcode.cn/problems/linked-list-cycle-ii/
[fd63dfc0a01c4a2d891ef66ea2738043.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/e9e8f80e2ce84bd89ea6d50c2cf5c919.png
[8c63c714f5b54613a8e1f18f2f60f885.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/969528c0834d40268497ac1911414d98.png