环形链表

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

链接：141. 环形链表 - 力扣（LeetCode） (leetcode-cn.com)

链表带环

方法：快慢指针

思路：

• 定义两个指针，一个为fast 一个为slow
• fast和slow从头开始遍历，fast每次走两步，slow每次走一步
• 如果存在环，fast和slow一定会相遇

• 若无环时：

  • 奇数个结点：fast->next == NULL结束
  • 偶数个结点：fast == NULL结束

  

• 而若有环，fast->next 和fast永远不为空

所以判断条件可以写成

while(fast && fast->next)
 //不可以写成
// while(fast->next && fast)

如果是无环的，则会通过while跳出，如果有环，不会跳出循环

fast->next不能在前面判断

错误写法

bool hasCycle(struct ListNode *head) {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
    
        //此处要fast放前面，不然当fast为NULL进行判断时，fast->next 是对空指针解引用，有问题
        while(fast->next && fast)
        {
            fast = fast->next ->next;
            slow = slow->next;
            if(fast == slow)
            {
                return true;
            }
        }
        return false;
}

正解代码

bool hasCycle(struct ListNode *head) {
    //定义快慢指针，从头开始遍历
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        //其中一个条件不满足就退出while,说明走到空
        while(fast && fast->next)
        {
            //fast一次走两步，slow一次走一步
            fast = fast->next ->next;
            slow = slow->next;
            if(fast == slow)
            {
                return true;
            }
        }
        //如果是无环的，通过while跳出循环返回fasle
        return false;
}

或者写成:

class Solution {
public:
    bool hasCycle(ListNode *head) {
      if(head == nullptr )
        return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        //终止条件:slow和fast相遇->说明有环 || fast提前走到空->说明无环
        while(slow != fast)
        {
            //其中一个条件满足就退出while,说明走到空
            if(fast ==nullptr || fast->next ==nullptr)
            {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        //说明有环
        return true; 
    }
};

问题延申1：fast一次走两步，slow一次走一步，为什么一定能相遇？会不会在环里错过，永远遇不上

fast一次走2步，slow一次走1步，fast和slow的距离不断减少1步

结论：slow一次走一步，fast一次走两步，如果存在环，slow和fast一定会在环内相遇

证明

问题延申2：fast一次走n步(n>2)，slow一次走一步，fast和slow能相遇吗

结论：fast一次走n步(n>2)，slow一次走一步，不一定会相遇

fast一次走n步，slow一次走1步，fast和slow的距离不断减少n-1步

例如：fast一次走3步

例如:fast一次走4步

\