判断链表是否存在环的程序问题

这是一个用快慢指针判断链表是否存在环的程序，leetcode 141请问为什么我这样写没法通过全部用例，未通过的用例是[1, 2](无环）

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr && fast != slow){
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast == nullptr || fast->next == nullptr){
            return false;
        }else{
            return true;
        }
    }
};

一开始的快慢指针都指向head，而while判断条件需要fast!=slow，也就是说不会进入while循环。需要修改fast指针为head->next，使得可进入while循环，在此之前需要先判断head->next是否空（或删掉fast!=slow这一判断条件，而在while循环内判断快慢指针是否相等）
以下是两种方式修改的代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr){
            return false;
        }
        ListNode *fast = head->next, *slow = head;
        while(fast != nullptr && fast->next != nullptr && fast != slow){
            slow = slow->next;
            fast = fast->next->next;
        }
        if(fast == nullptr || fast->next == nullptr) return false;
        return true;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow ) return true;
        }
        if(fast == nullptr || fast->next == nullptr) return false;
        return true;
    }
};

【以下回答由 GPT 生成】

问题分析：

这个问题是通过快慢指针判断链表是否存在环的问题。代码中使用了快指针和慢指针，快指针每次移动两步，慢指针每次移动一步，如果链表存在环，那么快指针最终会追上慢指针。

问题原因：

代码中的问题出在判断条件上。在 while 循环中，判断的条件是 fast != nullptr && fast->next != nullptr && fast != slow，当链表没有环时，快指针会先到达链表的末尾，然后 fast->next != nullptr 这个条件就不满足了，导致循环退出。但是根据题目要求，要判断链表中是否存在环，所以此时应该返回 false。

解决方案：

修改判断条件，当 fast 为空时，即快指针到达链表末尾时，返回 false。以下是修改后的代码：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
};

这样修改后，可以正确判断链表是否存在环，通过了所有的测试用例。

【相关推荐】

• 给你找了一篇非常好的博客，你可以看看是否有帮助，链接：环形链表【手绘漫画】面试必考之双指针（LeetCode 141）
• 除此之外, 这篇博客: 【LeetCode】394. 字符串解码：给定一个经过编码的字符串，返回它解码后的字符串中的 题目描述：给定一个经过编码的字符串，返回它解码后的字符串。 部分也许能够解决你的问题。