LeetCode如何找出链表中环的入口节点

问题背景

给定一个链表，其中可能存在一个环。环是由一个链表中的一个节点指向先前已经出现的节点，导致链表成环。找出环的入口节点就是要找到链表中指向环的那个节点。

解法一：使用哈希表

我们可以使用哈希表来解决这个问题。遍历链表的每个节点，若当前节点已经存在于哈希表中，则表明该节点是环的入口节点。否则，将当前节点加入哈希表中并继续遍历下一个节点，直到找到环的入口节点。

// C++示例代码
ListNode* detectCycle(ListNode* head) {
    unordered_set visited;
    ListNode* curr = head;
    while (curr) {
        if (visited.count(curr)) { // 当前节点已存在于哈希表中，是环的入口节点
            return curr;
        }
        visited.insert(curr); // 将当前节点加入哈希表
        curr = curr->next; // 遍历下一个节点
    }
    return nullptr; // 没有环的情况下返回nullptr
}

解法二：快慢指针

快慢指针是解决链表环相关问题的经典方法。我们可以使用两个指针，一个快指针每次移动两步，一个慢指针每次移动一步。如果链表存在环，则快指针和慢指针一定会在某个节点相遇。

1. 首先，我们需要找到快慢指针的相遇点。
2. 然后，让一个指针从链表的头节点开始，另一个指针从相遇点开始，两个指针都每次移动一步，直到它们相遇。
3. 当两个指针相遇时，它们相遇的节点就是环的入口节点。

// C++示例代码
ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    // 找到快慢指针的相遇点
    while (fast && fast->next) {
        fast = fast->next->next; // 快指针每次移动两步
        slow = slow->next; // 慢指针每次移动一步
        if (fast == slow) {
            break;
        }
    }
    // 链表不存在环的情况
    if (!fast || !fast->next) {
        return nullptr;
    }
    // 一个指针从头节点开始，另一个指针从相遇点开始
    ListNode* p1 = head;
    ListNode* p2 = slow;
    // 两个指针同时移动，直到相遇
    while (p1 != p2) {
        p1 = p1->next;
        p2 = p2->next;
    }
    return p1; // 返回相遇的节点，即环的入口节点
}

复杂度分析

解法一的时间和空间复杂度都为O(n)，其中n为链表中的节点数。

解法二的时间复杂度为O(n)，其中n为链表中的节点数。空间复杂度为O(1)。

通过使用哈希表或快慢指针，我们可以高效地找到链表中环的入口节点。