首页 > 试题广场 >

链表中环的入口节点

[编程题]链表中环的入口节点
  • 热度指数:134758 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
对于一个给定的链表,返回环的入口节点,如果没有环,返回null
拓展:
你能给出不利用额外空间的解法么?


说明:本题目包含复杂数据结构ListNode,点此查看相关信息
头像 数据结构和算法
发表于 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的长度为 展开全文