欢迎访问LeetCode题解合集

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

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

说明：不允许修改给定的链表。

进阶：

• 你是否可以使用 O(1) 空间解决此题？

示例 1：

[HTML_REMOVED]

[HTML_REMOVED]

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

示例 2：

[HTML_REMOVED]

[HTML_REMOVED]

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

示例 3：

[HTML_REMOVED]

[HTML_REMOVED]

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

• 链表中节点的数目范围在范围 $[0, 10^4]$ 内
• $-10^5 \le Node.val \le 10^5$
• pos 的值为 -1 或者链表中的一个有效索引

题解：

双指针。参考 环形链表 中判断是否存在环的方法。

假设在 s 在走到环的入口处时，走了 x 步，那么 f 在环中的某个位置，走了 2 * x 步，设 f 距离环入口还剩 y 步，假设这个环很大，那么其长度为 x + y 。那么当 s 走 y 步时，f 走了 2 * y 步，此时 s 和 f 第一次相遇，f 距离环的入口还剩 x 步。

在第一次相遇时，将 s 移动到链表头节点，然后两个指针一起移动 x 步，即可走到环的入口。

时间复杂度：$O(n)$

额外空间复杂度：$O(1)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if ( !head || !head->next ) return NULL;
        ListNode *s = head, *f = head->next;
        while ( s != f ) {
            if ( !f || !f->next ) return NULL;
            s = s->next;
            f = f->next->next;
        }
        s = head, f = f->next;
        while ( s != f ) {
            s = s->next;
            f = f->next;
        }
        return s;
    }
};
/*
时间：8ms，击败：91.10%
内存：7.4MB，击败：93.56%
*/