一、题目

二、解题思路

        判断链表是否有环可谓是一个常见的话题。其中，最简单的一种方式当属快慢指针法。慢指针每次前进一步，快指针每次前进两步。若二者相遇，则说明链表有环；若其中一个指针为空，则表明链表没有环。

        为何快慢指针一定能判断是否有环呢？我们可以如此思考，倘若有环，那么快慢指针最终都会进入环上。假设环的长度为 m，快慢指针最近的间距是 n，如下图所示。

        快指针每次前进两步，慢指针每次前进一步，所以每走一次，快慢指针的间距就会缩小一步。在图一中，走 n 次的时候二者会相遇；在图二中，走 m - n 次的时候二者会相遇。

三、代码实现

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

// 定义链表节点结构
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode* head) {
    if (head == nullptr)
        return false;

    // 快慢两个指针
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        // 慢指针每次走一步
        slow = slow->next;
        // 快指针每次走两步
        fast = fast->next->next;
        // 如果相遇，说明有环，直接返回true
        if (slow == fast)
            return true;
    }

    // 否则就是没环
    return false;
}

// 辅助函数：根据输入字符串构建链表
ListNode* buildList(const string& input, int pos) {
    vector<int> values;
    stringstream ss(input);
    string item;

    // 解析输入字符串，提取链表节点的值
    while (getline(ss, item, ',')) {
        values.push_back(stoi(item));
    }

    // 构建链表
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    vector<ListNode*> nodes;

    for (int val : values) {
        ListNode* node = new ListNode(val);
        nodes.push_back(node);
        if (head == nullptr) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }

    // 设置环
    if (pos != -1 && pos < nodes.size()) {
        tail->next = nodes[pos];
    }

    return head;
}

int main() {
    // 输入字符串
    string input = "3,2,0,-4";
    int pos = 1;

    // 构建链表
    ListNode* head = buildList(input, pos);

    // 检测链表是否有环
    bool result = hasCycle(head);

    // 打印结果
    cout << "Input: head = [" << input << "], pos = " << pos << endl;
    cout << "Output: " << (result ? "true" : "false") << endl;

    return 0;
}

        来思索这样一个问题，在此处，快慢指针中快指针每次行进两步，慢指针每次走一步。倘若慢指针仍然每次走一步，快指针每次走三步的话，能否进行判断呢？又或者快指针每次走 m 步，慢指针每次走 n 步，并且 m 不等于 n，在这样的情形下能不能够进行判断呢？

        在链表中判断是否有环的问题中，快慢指针是一种常用的方法。通常情况下，快指针每次走2步，慢指针每次走1步。我们来分析一下其他情况：

1. 慢指针每次走1步，快指针每次走3步

在这种情况下，快指针每次走3步，慢指针每次走1步。我们来分析一下是否能判断链表中是否有环。

分析：

• 相遇条件：假设链表中有环，快指针和慢指针最终会在某个节点相遇。

• 步数关系：快指针每次走3步，慢指针每次走1步。

• 环的长度：假设环的长度为L。

• 相遇点：假设慢指针在环中走了k步，快指针在环中走了3k步。

结论：

• 能判断：如果链表中有环，快指针和慢指针最终会在某个节点相遇。因为快指针每次走3步，慢指针每次走1步，快指针会比慢指针多走2步。如果链表中有环，快指针最终会追上慢指针。

2. 快指针每次走m步，慢指针每次走n步，并且m≠n

在这种情况下，快指针每次走m步，慢指针每次走n步，并且m ≠ n。我们来分析一下是否能判断链表中是否有环。

分析：

• 相遇条件：假设链表中有环，快指针和慢指针最终会在某个节点相遇。

• 步数关系：快指针每次走m步，慢指针每次走n步。

• 环的长度：假设环的长度为L。

• 相遇点：假设慢指针在环中走了k步，快指针在环中走了mk步。

结论：

• 能判断：如果链表中有环，快指针和慢指针最终会在某个节点相遇。因为快指针每次走m步，慢指针每次走n步，快指针会比慢指针多走m - n步。如果链表中有环，快指针最终会追上慢指针。

总结

• 慢指针每次走1步，快指针每次走3步：能判断链表中是否有环。

• 快指针每次走m步，慢指针每次走n步，并且m≠n：能判断链表中是否有环。

无论是快指针每次走3步，慢指针每次走1步，还是快指针每次走m步，慢指针每次走n步，并且m ≠ n，只要链表中有环，快指针最终会追上慢指针。因此，这些情况下都能判断链表中是否有环。