leetcode141：环形链表

题目链接

leetcode

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

C++ 代码

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

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

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：创建带环链表
ListNode* createList(const vector<int>& nums, int pos) {
    if (nums.empty()) return nullptr;

    vector<ListNode*> nodes;
    for (int val : nums) {
        nodes.push_back(new ListNode(val));
    }
    for (int i = 0; i < nums.size()-1; i++) {
        nodes[i]->next = nodes[i+1];
    }
    if (pos != -1) {
        nodes.back()->next = nodes[pos]; // 设置环
    }

    return nodes[0];
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    哈希表

    使用哈希表来存储所有已经访问过的结点，每次到达一个结点。
    如果该结点已经存在于哈希表中，则说明该链表是环形链表；
    否则，将该结点加入哈希表。
    重复这一过程，直到遍历完整个链表。

    时间复杂度：O(n)
        其中 n 是链表中的结点数。
        最坏情况下，遍历每个结点一次。
    空间复杂度：O(n)
        最坏情况下，将每个结点插入到哈希表中一次。
*/
class Solution_0 {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        while (head != nullptr) {
            if (set.count(head)) {
                return true;
            }
            set.insert(head);
            head = head->next;
        }
        
        return false;
    }
};

/*
    双指针

    两个指针从头开始扫描，第一个指针每次走一步，第二个指针每次走两步。
    如果走到空，说明不存在环；否则，说明存在环。
    为什么呢？
    假设链表存在环。
    当第一个指针走到环入口时，第二个指针已经走到环上的某个位置，距离环入口还差 x 步。
    由于第二个指针比第一个指针每次多走一步，所以第一个指针再走 x 步，两个指针就相遇了。

    时间复杂度：O(n)
        其中 n 是链表中的结点数。
        第一个指针在环上走不到一圈，所以第一个指针走的总步数小于链表总长度。
        第二个指针走的步数是第一个指针的两倍，总的时间复杂度是 O(n)。
    空间复杂度：O(1)
*/
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        ListNode *slow = head, *fast = head;
        // 快指针走到末尾时停止
        while (fast != nullptr && fast->next != nullptr) {
            // 慢指针走一步，快指针走两步
            slow = slow->next;
            fast = fast->next->next;
            // 若快慢指针相遇，则说明链表中有环
            if (slow == fast) {
                return true;
            }
        }

        // 链表中没有环
        return false;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> head_cases = {
        {3,2,0,-4},
        {1,2},
        {1}
    };
    vector<int> pos_cases = {
        1, 0, -1
    };

    for (size_t i = 0; i < head_cases.size(); i++) {
        auto& nums = head_cases[i];
        int pos = pos_cases[i];
        ListNode* head = createList(nums, pos);

        cout << "Input: head = ";
        printArray(nums);
        cout << ", pos = " << pos << endl;

        bool result = solution.hasCycle(head);
        cout << "Output: " << (result ? "true" : "false") << endl;
    }

    return 0;
}