142.环形链表 II
142.环形链表 II
zhou142.环形链表 II
142. 环形链表 II 题解
题目
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
思路
采用快慢指针的思路,但此法妙在如何计算head和环开始节点之间的距离。
声明两个指针,一个fast,一个slow。fast指针每次走两步,slow指针每次走一步。
那么会有两种情况:
一、如果fast走到了nullptr,那么就说明这个链表没有环
二、如果有环,那么fast和slow一定会会相遇,这便是第一次相遇
第一次相遇时我们记录然后退出,接下来思考如何计算得出环的第一个节点。
这是我们现在的情况
那么我们怎么求a呢?
假设slow指针前进的距离为x,那么fast指针前进的距离为2x
所以我们能得出:x = a+b
而fast比slow多走的距离,恰好就是环的长度,也就是c
所以,我们能得到等式:x = c
所以a+b = c
a = c-b
a
就是start到node的距离,c-b
就是slow指针还剩下的没走的环的距离
所以,我们让fast = start
,fast++
的同时slow++
当fast
和slow
第二次相遇时,就是node
的位置
代码
1 | class Solution { |
结束
小技巧,妙不可言…
Comment
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果