链表中环的入口节点

[编程题]链表中环的入口节点

热度指数：134760 时间限制：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 展开全文

悟空WK

发表于 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 展开全文