首页 > 试题广场 >

链表中环的入口结点

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

热度指数：646076 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： $n\le10000$ ， $1<=结点值<=10000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述:

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

输出描述:

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1

输入

{1,2},{3,4,5}

输出

说明

返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2

输入

{1},{}

输出

"null"

说明

没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3

输入

{},{2}

输出

说明

环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

leaves0924

发表于 2021-07-17 00:32:44

精华题解题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点示例1输入：{1,2},{3,4, 展开全文

牛客题解官

发表于 2022-04-22 11:27:21

精华题解题目主要信息: 给定一个链表，首先判断其是否有环，然后找到环的入口举一反三：学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM5.合并k个已排序的链表 BM6.判断链表中是否有环 BM8.链表中倒数最后k个节点 BM9.删除链表的倒数第n个节点 BM10.两个链表的第一个公共节展开全文

NumPy

发表于 2021-07-09 19:37:05

精华题解一、题目描述 NC3链表中环的入口结点题目描述：给定一条链表，若链表存在环，就请找到环的入口并返回入口的指针；若不存在环就返回null 二、算法1（哈希集合）解题思路：一个直观的想法就是用哈希表存下我们从链表头往下走路径所见过的节点指针，当出现已经记录过的节点时，这个节点就是环的入口节点代码实展开全文

不是江小白

发表于 2021-06-30 21:35:27

精华题解 1.易懂常规思路首先这题要我们找链表的环入口结点，最常规易懂的解法就是遍历整个链表结点，然后用哈希表来存储已访问过的结点，最后进行对比。若该结点已存在哈希表中，则代表该结点是我们要找的环形链表的入口结点；否则把结点添加到哈希表中，继续往下遍历。 2.图解哈希表解法这里我们就用题目中给的三个展开全文

Maokt

发表于 2021-06-28 18:17:04

精华题解算法思想一：双指针解题思路：我们使用两个指针，fast 与 slow。 1、它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。 2、当发现 sl 展开全文

江南好___

发表于 2021-07-01 01:41:08

精华题解描述题目描述给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点示例输入：{1, 展开全文

Peterliang

发表于 2021-07-15 21:36:01

精华题解题意分析这个题目给我们一个经过特殊处理的链表，这个链表分为两段，每一段包含一个链表的非环的部分和成环的部分。大多数人可能一开始看样例的时候会感觉不是很理解。其实你就只要知道它给你一个链表，这个链表中如果成环的话就说明这个链表里面存在相同的结点。也就是转化为问你给出一个链表，需要你判断这个链表里面展开全文

牛一霸

发表于 2021-07-03 23:58:41

精华题解题目：链表中环的入口结点输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点示例1：输入：{1,2},{3,4,5}，返回值：3 说明：返回展开全文

一颗闪闪发亮的马路星

发表于 2020-02-16 04:13:48

写在前面：这份解法是搬运，图片也是原回答评论区网友贡献，非本人原创：https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation. 展开全文

牛客题解官

发表于 2020-06-01 14:55:08

#描述这是一篇针对初学者的题解，共用两种方法解决。知识点：单链表，哈希，双指针难度：二星 #题解题目抽象：给定一个单链表，如果有环，返回环的入口结点，否则，返回nullptr ##方法一：哈希法遍历单链表的每个结点如果当前结点地址没有出现在set中，则存入set中否则，出现在set 展开全文

中工升达预备毕业生

发表于 2019-10-01 14:05:12

看到这题时，无从下手...再看书时，书上逻辑思维真的太棒了，想问题的思路很nice！思路：1.判断链表中有环 -> 2.得到环中节点的数目 -> 3.找到环中的入口节点 /* public class ListNode { int val; ListNode next 展开全文

数据结构和算法

发表于 2021-06-30 17:03:14

之前讲过《NC4 判断链表中是否有环》只需要判断是否有环即可，而今天这题如果有环还要找出环的入口，这题我们可以使用两种方式来解决 1，快慢指针解决在前面我们提到过快慢指针，判断是否有环。如果有环，在来找环的入口。如果没环直接返回null即可，我们假设是有环的，那么会有两种情况，一种是O型，一展开全文