给一个长度为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，点此查看相关信息
两次while 麻烦点 。依次放map，再出现就是入口
public class Solution {
public ListNode EntryNodeOfLoop(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != slow) {
if (fast == null || fast.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
HashMap<Integer, Integer> map = new HashMap<>();
ListNode curr = head;
while (!map.containsKey(curr.val)) {
map.put(curr.val, curr.val);
curr = curr.next;
}
return curr;
}
}
发表于 2025-02-28 11:29:39
回复(0)
破坏链表：
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode const_tail = new ListNode(999);
while(pHead != null){
if(pHead.next == const_tail) return pHead;
ListNode temp = pHead.next;
pHead.next = const_tail;
pHead = temp;
}
return null;
} 不破坏链表 public ListNode EntryNodeOfLoop(ListNode pHead) {
HashSet<ListNode> list = new HashSet<>();
while(pHead != null){
if(list.contains(pHead.next)) return pHead.next;
list.add(pHead);
pHead = pHead.next;
}
return null;
}
发表于 2024-08-17 12:41:14
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
// 左程云老师讲过这道题，采用快慢指针，快指针一次走两个结点，慢指针一次走一个结点，若二者能相遇，则有环，否则无环
// 若有环，在快慢指针相遇之后，令快指针返回head，降速成一次走一个结点，当二者再次相遇的结点就是成环结点
// 算法的时间复杂度O(N)，额外空间复杂度O(1)
// 1.先判断链表为空的情况
if (pHead == null) {
return null;
}
// 2.确定链表不为空
ListNode fast = pHead;
ListNode slow = pHead;
boolean hasCycle = false;
// 注意！这里不能用while而应该用do while
// 因为fast和slow初始化就是相同的，用while会直接跳出循环
do {
// 3.如果链表是无环的，那么fast一定先走到null，直接return false即可
if (fast.next == null || fast.next.next == null) {
// 这里一定不会报空指针异常，因为先判断fast.next == null，若满足，则直接return false，不会继续判断后面
return null;
}
// 4.快指针一次走两个结点，慢指针一次走一个结点
fast = fast.next.next;
slow = slow.next;
} while (fast != slow);
// 5.若因为fast == slow而结束循环，说明fast和slow二者相遇了，说明链表有环
// 若有环，则令快指针返回head，降速成一次走一个结点，当二者再次相遇的结点就是成环结点
fast = pHead;
// 注意！这里不能用do while而应该用while
// 假如成环结点就是pHead，用do while会错过一次判断
while (fast != slow) {
// 6.快指针降速为一次走一个结点，慢指针依然是一次走一个结点
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
发表于 2024-07-26 23:15:20
回复(0)
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
SetListNode> set = new HashSet();
while(pHead != null){
if(!set.add(pHead)){
break;
}
pHead = pHead.next;
}
return pHead;
}}
发表于 2024-05-31 10:57:51
回复(0)
难绷，快慢指针我只会上一题简单版，这题完全瞎碰
public ListNode EntryNodeOfLoop(ListNode pHead) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
int i=0;
while(pHead!=null){
i++;
if( map.put(pHead.hashCode(),i)!=null){
return pHead;
}
pHead=pHead.next;
}
return null;
}
编辑于 2024-04-05 01:47:21
回复(0)
public ListNode EntryNodeOfLoop(ListNode pHead) {
Integer num = null;
HashMap<Integer,Integer> map = new HashMap<>();
while (pHead != null ) {
if (map.containsKey(pHead.val)) {
num = pHead.val;
break;
} else {
map.put(pHead.val, 1);
}
pHead = pHead.next;
}
if (num == null) {
return null;
}
ListNode node = new ListNode(num);
return node;
}
编辑于 2024-02-28 22:03:16
回复(0)
public class Solution {
//链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度
//判断有没有环，返回相遇的地方
public ListNode hasCycle(ListNode head) {
//先判断链表为空的情况
if (head == null)
return null;
//快慢双指针
ListNode fast = head;
ListNode slow = head;
//如果没环快指针会先到链表尾
while (fast != null && fast.next != null) {
//快指针移动两步
fast = fast.next.next;
//慢指针移动一步
slow = slow.next;
//相遇则有环，返回相遇的位置
if (fast == slow)
return slow;
}
//到末尾说明没有环，返回null
return null;
}
public ListNode EntryNodeOfLoop(ListNode pHead) {
ListNode slow = hasCycle(pHead);
//没有环
if (slow == null)
return null;
//快指针回到表头
ListNode fast = pHead;
//再次相遇即是环入口
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
发表于 2024-02-20 21:54:08
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
//如果没有节点或者只有一个节点，就不可能有环入口，直接返回null
if (pHead == null || pHead.next == null){
return null;
}
//我定义了一个快指针，一个慢指针，快指针每次跑两个节点，慢指针每次跑一个节点
ListNode fast = pHead;
ListNode low = pHead;
while (fast.next != null && fast.next.next != null){
low = low.next;
fast = fast.next.next;
if (low == fast){ //说明有环路
low = pHead; //让慢指针重新指向头节点，这次快慢指针每次都跑一个节点
while(low != fast){
low = low.next;
fast = fast.next;
}
return low;
}
}
//如果能走到这里，就说明没有环路，也返回null
return null;
}
}
发表于 2023-11-26 23:51:52
回复(0)
笔试遇到的题，四十分钟没做出来，回来趟床上突然想到这个方法。拍断大腿。
因为测试集全是正数，直接将走过的点置为相反数就行了
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
while(pHead != null && pHead.val > 0){
pHead.val = -pHead.val;
pHead = pHead.next;
}
if(pHead == null){
return null;
}else{
pHead.val = -pHead.val;
return pHead;
}
}
}
发表于 2023-11-24 21:17:44
回复(1)
快慢指针
假设 从起点到环入口长度为a，环长度为b，相遇点为k，
那么 a+n圈的b，都能找到入口
快指针走的距离：a + nb + k
慢指针走的距离：a + mb +k
快指针速度是慢指针的2倍，相减，慢指针 = 快指针-慢指针 = （相差的n圈）* b
因为a+nb都能找到入口，则再走a步就可以了，让慢指针会到原点，再走a长度就是环入口
发表于 2023-10-25 15:15:03
回复(0)
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
while(pHead != null){
if(pHead.val < 0){
pHead.val = pHead.val + Integer.MAX_VALUE;
return pHead;
}else{
pHead.val = pHead.val - Integer.MAX_VALUE;
pHead = pHead.next;
}
}
return null;
}
}
思路：走过更新数据为负数，当值为负数表示有环，把数还原回来，在这里使用了int最大值
发表于 2023-10-11 23:33:36
回复(2)
这个和上个判断是否有环的题没什么区别
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
HashSet<ListNode> hasCycleSet = new HashSet<>();
while(pHead != null){
if(hasCycleSet.contains(pHead)){
// 下一个节点已记录
return pHead;
}else{
// 下一个节点未记录
hasCycleSet.add(pHead);
}
pHead = pHead.next;
}
return null;
}
}
发表于 2023-09-26 02:10:24
回复(0)
问题信息
难度：
290条回答
3157收藏
132822浏览
通过挑战的用户
查看代码-
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; } }