调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

 

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

 

进阶:

  • 你是否可以不用额外空间解决此题?

 

通过次数
49.5K
提交次数
87.6K
通过率
56.5%


相关企业

提示 1
这个问题实际上可以分为两个部分。首先,检测链表是否有循环。第二,找出循环开始的位置。

提示 2
要确定是否有一个循环,请尝试“快行指针”方法。让一个指针比另一个指针快。

提示 3
你可以使用两个指针,一个指针移动速度是另一个指针的两倍。如果有环,两个指针会碰撞。它们将同时降落在同一地点。它们在哪里相遇?为什么呢?

提示 4
如果你还没有确定两个指针的起始位置,请尝试使用链表1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> ?,其中 ? 链接到另一个节点。试着让 ? 成为第一个节点(即9指向1,使得整个链表是一个循环)。然后让 ? 成为节点2,然后成为节点3,然后成为节点4。这一模式是什么?你能解释一下为什么会这样吗?

评论 (0)

《程序员面试金典(第 6 版)》独家授权
本书是原谷歌资深面试官的经验之作,帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的,帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
head =
[3,2,0,-4]
pos =
1
Source