# LeetCode 141 - 环形链表

🧠 题目简介

LeetCode 141 - 环形链表

给定一个链表的头节点 head，判断链表中是否有环。

• 如果链表中存在环，则返回 true。
• 否则，返回 false。

💡 解题思路：快慢指针（Floyd 判圈法）

我们使用两个指针：

• slow 每次走一步；
• fast 每次走两步。

✅ 结论：

• 如果链表中存在环，fast 和 slow 最终会在环中相遇。
• 如果没有环，fast 会走到 NULL，此时返回 false。

🧱 C++ 实现

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

        while (slow != fast) {
            if (!fast || !fast->next) return false;
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

完整 C++ 输入输出 + 环形链表判断代码

#include <iostream>
#include <unordered_set>
using namespace std;

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

// 判断链表中是否存在环（Floyd 判圈法）
bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    ListNode* slow = head;
    ListNode* fast = head->next;
    while (slow != fast) {
        if (!fast || !fast->next) return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

/**
 * 构造一个链表，并在指定位置创建环（可选）。
 *
 * @param vals 包含链表各节点值的整数数组（按顺序）
 * @param pos  决定是否创建环的参数：
 *             - pos == -1 表示不创建环；
 *             - pos >= 0 表示将链表的最后一个节点连接到位置为 pos 的节点上形成环。
 *
 * @return 返回构建好的链表的头节点指针。
 */
ListNode* createListWithCycle(const vector<int>& vals, int pos) {
    // 如果输入数组为空，直接返回空链表
    if (vals.empty()) return nullptr;

    // 创建链表的头节点（第一个节点）
    ListNode* head = new ListNode(vals[0]);
    // 当前节点指针，用于逐步构建链表
    ListNode* curr = head;
    // 用于记录“环的入口”节点的指针，初始为空
    ListNode* cycleEntry = nullptr;
    
    // 从第二个元素开始，依次构造链表其余部分
    for (int i = 1; i < vals.size(); ++i) {
        curr->next = new ListNode(vals[i]);
        curr = curr->next;

        // 如果当前索引正好是 pos，说明这是指定的“环入口”
        if (i == pos) cycleEntry = curr;
    }

    // 特殊情况处理：如果 pos 是 0，即指定“环入口”为头节点
    if (pos == 0) cycleEntry = head;
    
    // 如果设置了环入口，就将当前（最后一个）节点的 next 指向它，形成环
    if (cycleEntry) curr->next = cycleEntry;

    return head;
}

int main() {
    vector<int> input = {3, 2, 0, -4};
    int pos = 1; // 指尾节点连接到哪个位置（-1 表示不连）

    ListNode* head = createListWithCycle(input, pos);
    cout << (hasCycle(head) ? "true" : "false") << endl;

    return 0;
}