142_环形链表_II

类型：链表

环形链表 II 💛

https://leetcode-cn.com/problems/linked-list-cycle-ii/

❓ 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。不允许修改给定的链表。

💡 哈希

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        hashMap = {}
        while head:
            if head in hashMap:
                return head
            else:
                hashMap[head] = True
            head = head.next
        return None

时间复杂度：O(n)，空间复杂度：O(n)

💡 快慢指针

从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

时间复杂度：O(n)，空间复杂度：O(1)