题目简介:
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
为了表示给定链表中的环,我们使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos
是 -1
,则在该链表中没有环。
说明:不允许修改给定的链表。
示例 1:
1 | 输入:head = [3,2,0,-4], pos = 1 |
进阶:
你是否可以不用额外空间解决此题?
思路:
在昨天的题目上进行修改,这回需要找的是入环点。
我们可以根据上图进行数学公式的推导:
设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b 的距离与 quick 指针相遇,此时,quick 指针已经走完了环的 n 圈,因此它走过的总距离为 a + n(b + c) + b = a + (n + 1)b + nc
。
因为任意时刻,quick 指针走过的距离都是 slow 指针的两倍,所以a + (n + 1)b + nc = 2(a + b)
,即a = c + (n - 1)(b + c)
。也就是从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。
所以当两个指针相遇时,我们可以定义一个res
指针指向head
,并与slow
指针同时进行移动,当它们相遇时,即为入环点。
代码如下:
1 | /** |