LeetCode 141 题：环形链表判断的两种解法

环形链表判断

在计算机科学中，链表是一种基础数据结构。正常链表以空指针结尾，而环形链表的某个节点指向已存在的节点，形成循环。

解法一：哈希表法

解题思路

记录经过的节点，若遇到重复则存在环。

bool hasCycle(ListNode *head) {
    unordered_set<ListNode*> visited;
    while (head != nullptr) {
        if (visited.count(head)) {
            return true;
        }
        visited.insert(head);
        head = head->next;
    }
    return false;
}

性能分析

指标	值	说明
时间复杂度	O(n)	最坏情况遍历整个链表
空间复杂度	O(n)	需存储所有访问过的节点

解法二：快慢指针法

解题思路

受龟兔赛跑启发，两个指针以不同速度遍历。若存在环，快指针终将追上慢指针。

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