0142. 环形链表 II #
- 标签:链表、双指针
- 难度:中等
题目大意 #
描述:给定一个链表的头节点 head
。
要求:判断链表中是否有环,如果有环则返回入环的第一个节点,无环则返回 None
。
说明:
- 链表中节点的数目范围在范围 $[0, 10^4]$ 内。
- $-10^5 \le Node.val \le 10^5$。
pos
的值为-1
或者链表中的一个有效索引。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:快慢指针(Floyd 判圈算法) #
- 利用两个指针,一个慢指针
slow
每次前进一步,快指针fast
每次前进两步(两步或多步效果是等价的)。 - 如果两个指针在链表头节点以外的某一节点相遇(即相等)了,那么说明链表有环。
- 否则,如果(快指针)到达了某个没有后继指针的节点时,那么说明没环。
- 如果有环,则再定义一个指针
ans
,和慢指针一起每次移动一步,两个指针相遇的位置即为入口节点。
这是因为:假设入环位置为 A
,快慢指针在 B
点相遇,则相遇时慢指针走了 $a + b$ 步,快指针走了 $a + n(b+c) + b$ 步。
因为快指针总共走的步数是慢指针走的步数的两倍,即 $2(a + b) = a + n(b + c) + b$,所以可以推出:$a = c + (n-1)(b + c)$。
我们可以发现:从相遇点到入环点的距离 $c$ 加上 $n-1$ 圈的环长 $b + c$ 刚好等于从链表头部到入环点的距离。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。