首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
链表中环的入口节点
[编程题]链表中环的入口节点
热度指数:134758
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32M,其他语言64M
算法知识视频讲解
对于一个给定的链表,返回环的入口节点,如果没有环,返回null
拓展:
你能给出不利用额外空间的解法么?
说明:本题目包含复杂数据结构ListNode,
点此查看相关信息
马上挑战
算法知识视频讲解
提交运行
算法知识视频讲解
添加笔记
求解答(0)
邀请回答
收藏(554)
分享
提交结果有问题?
241个回答
30篇题解
开通博客
数据结构和算法
发表于 2021-03-19 23:01:38
精华题解
这题可以参照《判断链表中是否有环》 ,答案我之前写过《链表是否有环3种方式解决》 ,这两道题有非常大的相似地方。 1,快慢指针解决 在前面我们提到过快慢指针,先判断是否有环,如果有环,在来找环的入口。我们假设是有环的,那么会有两种情况,我们来画个图看一下 1,环很大 假如他们在相遇点相遇了,那么慢指
展开全文
han1254
发表于 2021-03-02 09:36:41
精华题解
判断一个链表是否存在环,有一个Floyd判圈法 tortoise = top hare = top forever: if hare == end : return 'No Loop Found' hare = hare.next if hare
展开全文
去种田的程序员
发表于 2020-05-31 12:53:47
题目描述:对于一个给定的链表,返回环的入口节点,如果没有环,返回null 快慢指针方法:将两指针分别放在链表头(X)和相遇位置(Z),并改为相同速度推进,则两指针在环开始位置相遇(Y),如图所示。 证明过程:X,Y,Z分别为链表起始位置,环开始位置和两指针相遇位置,由快
展开全文
LifelongCode
发表于 2021-01-18 21:50:34
第一步,找环中相汇点。分别用p1,p2指向链表头部, p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。 那么我们可以知道fast指针走过a+b+c+b slow指针走过a+b 那么2*(a+b) = a+b+c+b 所以a = c 那么此时让slow回到起点,fast依然
展开全文
Lxdll
发表于 2020-09-09 19:40:25
思路:从前往后遍历链表,将每个节点的next指向自己,然后当遍历到后面有节点的next为自己的话,就说明有环存在,然后我们将对应元素输出就可以。这种方法的缺点是破坏了当前的链表结构,大家可以根据题意去选择方法。 function detectCycle( head ) { // 链表为空
展开全文
小洋芋热爱NLP
发表于 2021-02-25 20:14:26
- 1、题目描述: - 2、题目链接:https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tpId=117&tqId=37713&rp=1&ru=%2Factivity%2Foj&qru
展开全文
悟空GGG
发表于 2020-11-27 08:43:56
牛客题霸NC3链表中环的入口节点Java题解https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tpId=117&&tqId=34924&rp=1&ru=/ta/job-code-hig
展开全文
菜鸟也要飞的高
发表于 2020-11-19 19:26:52
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; *
展开全文
华科不平凡
发表于 2020-09-23 15:43:20
两步走: 利用快慢指针判断是否存在环——如果快指针最后指向NULL,则不存在环,否则存在环 利用双指针判断入口节点 参照下图,假设图中存在环且快慢指针在C处相遇,设|AB|=a, |BC|=b, |CB|=c,有2(a+b)=a+b+n(b+c),推出a=n(b+c)-b,因此让两个指针分别从A
展开全文
看机会)p
发表于 2021-03-24 23:37:36
324134134143428
发表于 2020-09-08 10:47:14
错误描述 方法解释: 遍历所有节点,将遍历过的节点的next设置为特殊节点X,终止条件:如果遍历到某节点的next==X,则说明此节点遍历过了,但是又遍历到它了,ok,return否则,直接return None 代码: class ListNode: def __init__(self
展开全文
不经历怎么能成长
发表于 2021-04-15 16:07:29
设置两个指针一个快指针每次走两步(fast->next->next),一个慢指针一次走一步(low->next)。 如果链表中没有环它们最后肯定不相遇,反之它们一定会在环中相遇。 如上图链表中有环,从x点出发,环的入口为点y,它们最后会在z点相遇。 设x到y长度为a,y到z的长度为
展开全文
问题信息
链表
双指针
难度:
241条回答
554收藏
37221浏览
热门推荐
通过挑战的用户
牛客20133...
2023-03-13 12:15:09
K乀
2023-02-28 21:58:48
已注销
2023-02-16 14:42:45
GeekExp...
2023-02-16 14:22:42
虫虫的乖小狗
2023-01-23 21:55:06
相关试题
神奇的数字
排序
双指针
评论
(46)
和为S的两个数字
数组
数学
双指针
评论
(1508)
来自
“一战通offer”互联...
最小面积子矩阵
动态规划
双指针
前缀和
评论
(44)
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题
import java.util.*; /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { } }
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { } };
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode类 # @return ListNode类 # class Solution: def detectCycle(self , head ): # write code here
/* * function ListNode(x){ * this.val = x; * this.next = null; * } */ /** * * @param head ListNode类 * @return ListNode类 */ function detectCycle( head ) { // write code here } module.exports = { detectCycle : detectCycle };
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # # @param head ListNode类 # @return ListNode类 # class Solution: def detectCycle(self , head ): # write code here
package main import . "nc_tools" /* * type ListNode struct{ * Val int * Next *ListNode * } */ /** * * @param head ListNode类 * @return ListNode类 */ func detectCycle( head *ListNode ) *ListNode { // write code here }
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * * @param head ListNode类 * @return ListNode类 */ struct ListNode* detectCycle(struct ListNode* head ) { // write code here }