Day15-环形链表 II

📌 题目描述

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

示例：

1
2
3

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

💡 解题思路

本题是经典的“快慢指针”问题。

判断是否有环：
- 使用两个指针，slow 每次移动一步，fast 每次移动两步。
- 如果 fast 和 slow 相遇，说明链表中存在环。
找到入环点：
- 当 fast 和 slow 相遇时，将其中一个指针移到链表头部，另一个指针保持在相遇点。
- 两个指针每次都移动一步，最终相遇的节点即为入环点。

✅ JavaScript 实现

var detectCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
};

🟣 Swift 实现

class Solution {
    func detectCycle(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head

        while let nextFast = fast?.next?.next, let nextSlow = slow?.next {
            slow = nextSlow
            fast = nextFast
            if slow === fast {
                var ptr = head
                while ptr !== slow {
                    ptr = ptr?.next
                    slow = slow?.next
                }
                return ptr
            }
        }
        return nil
    }
}

🧠 思考拓展

如果链表中存在多个环，算法是否仍然适用？
如何在不修改链表结构的情况下检测环？
能否在 O(1) 空间复杂度下解决此问题？