正解在这里:假设 头到环入口的距离是a, 快慢指针相遇距离环入口距离是b,环的长度是r,快指针走过的距离为f,慢指针走过的距离是s,快指针绕环走了m圈,慢指针绕环走了n圈(m>n),则:
f = a + mr + b;
s = a + nr + b;
由于快指针是慢指针的2倍,则f=2s;三式叠加可得:2(a + nr + b)= a + mr +b;进而推导出: a = (m - 2n)r - b;提取一个r出来,则 a = (m - 2n + 1)r + r - b;又因为(m-2n+1)r就是换的若干倍,那么a和b的关系就是从相遇点算 r-b=a,这也就是网上很多解法是,先用快慢指针算出相遇点,然后让其中一个指针指向头,再次相遇就是环入口的解法的原因。
链表找出环的入口给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。说明:不允许修改给定的链表。你是否可以不用额外空间解决此题? https://leetcode-...