240 发简信
IP属地:台湾
  • 正解在这里:假设 头到环入口的距离是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-...

  • 一年前的博客,最近也在追这个问题,实际上作者的解法适合物理学上的追逐问题,但不适合链表,原因是,物理学上的追逐的解是连续的,而链表的解离散的整数解,这会导致快指针在慢指针走完环一圈之内追上这个结论是错误的。物理上在一圈内追上,快慢指针走的距离可能是小数,但是在链表中,当追上的距离是小数这种情况是不存在的,只能再走N圈直到快慢指针走的距离相同切都是整数解。

    链表找出环的入口

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。说明:不允许修改给定的链表。你是否可以不用额外空间解决此题? https://leetcode-...

  • 多愁善感的菇凉,我以前蛮喜欢听这首歌,特别周末一个人的时候听,听着听着就感觉悲伤在蔓延,现在一个人的时候,会听摇滚

    逆流成河

    斑驳的夜色在说什么 谁能告诉我如何选择 每当我想起分离时刻 悲伤就逆流成河 你给的温暖属于谁呢 谁又会在乎我是谁呢 每当我想起你的选择 悲伤就逆流成河 失去了你也是种获得 一...