每日一题

昨天玩cycleGAN忘记刷题了…
今天快速水一道题后洗澡。

每日一题系列_算法提升

题目: https://leetcode.cn/problems/linked-list-cycle/

首先，第一个想到的是开一个哈希表，存一下访问过的地址，如果到达尾指针，还没有经过访问过的地点，那么久说明无环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map vis;
        while (head != nullptr) {
            if (vis[head])
                return true;
            vis[head] = true;
            head = head->next;
        }
        return false;
    }
};

方法二、快慢指针，具体可以看题解

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