剑指 Offer II 022. 链表中环的入口节点

题目链接：剑指 Offer II 022. 链表中环的入口节点

方法一：哈希

解题思路

统计走过的节点，当第一次遇到重复的节点时，即为入口节点，否则为 \(null\)。

代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode*, bool> cache;
        while (head) {
            if (cache.count(head)) break;
            cache[head] = true;
            head = head->next;
        }
        return head;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)。

方法二：快慢指针

解题思路

Krahets题解

代码

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (true) {
            if (!fast || !fast->next) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        fast = head;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。