代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
提示：
[0, 104] 内-105 <= Node.val <= 105pos 的值为 -1 或者链表中的一个有效索引先利用快慢指针判断链表是否有环，没有环则直接返回 null。
若链表有环，我们分析快慢相遇时走过的距离。
对于慢指针，走过的距离为 S=X+Y ①；快指针走过的距离为 2S=X+Y+N(Y+Z) ②。如下图所示，其中 N 表示快指针与慢指针相遇时在环中所走过的圈数，而我们要求的环入口，也即是 X 的距离：
我们根据式子 ①②，得出 X+Y=N(Y+Z) => X=(N-1)(Y+Z)+Z。
当 N=1(快指针在环中走了一圈与慢指针相遇) 时，X=(1-1)(Y+Z)+Z，即 X=Z。此时只要定义一个 p 指针指向头节点，然后慢指针与 p 开始同时走，当慢指针与 p 相遇时，也就到达了环入口，直接返回 p 即可。
当 N>1时，也是同样的，说明慢指针除了走 Z 步，还需要绕 N-1 圈才能与 p 相遇。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
has_cycle = False
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow == fast:
has_cycle = True
break
if not has_cycle:
return None
p = head
while p != slow:
p, slow = p.next, slow.next
return p
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
boolean hasCycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) {
return null;
}
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
