给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围： 
，
要求：空间复杂度 )
，时间复杂度 )
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：
可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
[编程题]链表中环的入口结点
- 热度指数：679279 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
输出描述:
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
示例1
输入
{1,2},{3,4,5}输出
3
说明
返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
示例2
输入
{1},{}输出
"null"
说明
没有环，返回对应编程语言的空结点，后台程序会打印"null"
示例3
输入
{},{2}
输出
2
说明
环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2
说明：本题目包含复杂数据结构ListNode，点此查看相关信息
package main
import "fmt"
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
var addrlist = make(map[*ListNode]int)
if pHead == nil || pHead.Next == nil {
return nil
}
for pHead != nil {
fmt.Println(pHead.Val)
addrlist[pHead] += 1
if addrlist[pHead] == 3 {
return pHead
}
pHead = pHead.Next
}
return nil
}
还好这些例子简单
发表于 2023-08-16 00:59:24
回复(0)
如果可以拆链表的链子，那么一直拆链子就可以拆掉自己的节点。每次走一个节点就过河拆桥，最后一定会走到尽头。为了区分普通链表，需要把next设为自己来标记已经走过
package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
p := pHead
if p.Next == nil {
return nil
}
for p.Next != nil {
if p.Next == p {
return p
}
n := p.Next
p.Next = p
p = n
}
return nil
}
发表于 2023-06-19 11:32:45
回复(0)
package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
// 快慢指针
slow, fast := pHead, pHead
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
if slow == fast {
fast = pHead
for fast != slow {
slow, fast = slow.Next, fast.Next
}
return slow
}
}
return nil
}
发表于 2023-02-04 12:30:51
回复(0)
package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
slow, fast, p := pHead, pHead, pHead
for fast != nil && fast.Next != nil{
slow = slow.Next
fast = fast.Next.Next
if slow == fast{
for p != slow{
p = p.Next
slow = slow.Next
}
return p
}
}
return nil
}
发表于 2022-06-18 19:52:08
回复(0)
设head到环节点长度为a,环长度为b
1. 设fast走了f,slow走了s,任何时候满足 f = 2s
2. 相遇时，fast肯定已经在环内多走了几圈，设fast多走的圈数为n，此时满足f = s + nb.
3. 设slow节点每次路过环节点时走的路径为k，在环中走了m圈，k = a + mb，2中相遇后路过环节点k' = a + nb。所以 k' = a + s。也就是相遇后，s再走a就到环节点。
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
fast, slow := pHead, pHead
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
break
}
}
if fast == nil || fast.Next == nil {
return nil
}
fast = pHead
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
发表于 2022-04-25 19:03:56
回复(0)
这种数据量级有更简单的办法
package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
var num int = 1
var lable int = num << 63
for node := pHead; node != nil ; node = node.Next {
if node.Val & lable == lable {
node.Val ^= lable
return node
} else {
node.Val |= lable
}
}
return nil
}
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
var num int = 1
var lable int = num << 63
for node := pHead; node != nil ; node = node.Next {
if node.Val & lable == lable {
node.Val ^= lable
return node
} else {
node.Val |= lable
}
}
return nil
}
发表于 2021-10-05 23:56:50
回复(0)
package main
func EntryNodeOfLoop(pHead *ListNode) *ListNode{
if pHead == nil {return pHead}
fast, slow := pHead, pHead
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
slow = pHead
for fast != slow {
fast = fast.Next
slow = slow.Next
}
return fast
}
}
return nil
}
发表于 2021-09-03 22:28:13
回复(0)
问题信息
难度：
10条回答
3157收藏
132824浏览
通过挑战的用户
查看代码-
2023-03-14 12:34:52 -
2023-03-11 10:31:53
-
2023-02-10 17:17:10 -
2022-10-14 14:20:28 -
2022-09-21 16:34:31
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
当第二个指针指向环的入口结点时，第一个指针已经围绕着环走了一圈又回到了入口结点。
public class 链表中环的入口结点 { //找到一快一满指针相遇处的节点，相遇的节点一定是在环中 public static ListNode meetingNode(ListNode head) { if(head==null) return null; ListNode slow = head.next; if(slow==null) return null; ListNode fast = slow.next; while (slow != null && fast != null) { if(slow==fast){ return fast; } slow=slow.next; fast=fast.next; if(fast!=slow){ fast=fast.next; } } return null; } public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode meetingNode=meetingNode(pHead); if(meetingNode==null) return null; // 得到环中的节点个数 int nodesInLoop=1; ListNode p1=meetingNode; while(p1.next!=meetingNode){ p1=p1.next; ++nodesInLoop; } // 移动p1 p1=pHead; for(int i=0;i<nodesInLoop;i++){ p1=p1.next; } // 移动p1，p2 ListNode p2=pHead; while(p1!=p2){ p1=p1.next; p2=p2.next; } return p1; } }