首页 > 链表中环的入口结点
开通博客写题解
头像 leaves0924
发表于 2021-07-17 00:32:44
题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点示例1输入：{1,2},{3,4, 展开全文
去ta的博客 赞 (122) 回复(18) 收起
头像 牛客题解官
发表于 2022-04-22 11:27:21
题目主要信息: 给定一个链表，首先判断其是否有环，然后找到环的入口 举一反三： 学习完本题的思路你可以解决如下题目： BM4.合并有序链表 BM5.合并k个已排序的链表 BM6.判断链表中是否有环 BM8.链表中倒数最后k个节点 BM9.删除链表的倒数第n个节点 BM10.两个链表的第一个公共节 展开全文
去ta的博客 赞 (84) 回复(27) 收起
头像 幸福的火龙果在干饭
发表于 2021-07-09 19:37:05
一、题目描述 NC3链表中环的入口结点题目描述：给定一条链表，若链表存在环，就请找到环的入口并返回入口的指针；若不存在环就返回null 二、算法1（哈希集合） 解题思路： 一个直观的想法就是用哈希表存下我们从链表头往下走路径所见过的节点指针，当出现已经记录过的节点时，这个节点就是环的入口节点 代码实 展开全文
去ta的博客 赞 (73) 回复(9) 收起
头像 不是江小白
发表于 2021-06-30 21:35:27
1.易懂 常规思路 首先这题要我们找链表的环入口结点，最常规易懂的解法就是遍历整个链表结点，然后用哈希表来存储已访问过的结点，最后进行对比。 若该结点已存在哈希表中，则代表该结点是我们要找的环形链表的入口结点；否则把结点添加到哈希表中，继续往下遍历。 2.图解 哈希表解法 这里我们就用题目中给的三个 展开全文
去ta的博客 赞 (42) 回复(2) 收起
头像 Maokt
发表于 2021-06-28 18:17:04
算法思想一：双指针 解题思路： 我们使用两个指针，fast 与 slow。 1、它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。 2、当发现 sl 展开全文
去ta的博客 赞 (18) 回复(1) 收起
头像 江南好___
发表于 2021-07-01 01:41:08
描述 题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。 输入描述： 输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表 返回值描述： 返回链表的环的入口结点即可。而我们后台程序会打印这个节点 示例 输入：{1, 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 Peterliang
发表于 2021-07-15 21:36:01
题意分析 这个题目给我们一个经过特殊处理的链表，这个链表分为两段，每一段包含一个链表的非环的部分和成环的部分。大多数人可能一开始看样例的时候会感觉不是很理解。其实你就只要知道它给你一个链表，这个链表中如果成环的话就说明这个链表里面存在相同的结点。也就是转化为问你给出一个链表，需要你判断这个链表里面 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛一霸
发表于 2021-07-03 23:58:41
题目：链表中环的入口结点 输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台将这2个会组装成一个有环或者无环单链表 返回值描述：返回链表的环的入口结点即可。而我们后台程序会打印这个节点 示例1：输入：{1,2},{3,4,5}，返回值：3 说明：返回 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 一颗闪闪发亮的马路星
发表于 2020-02-16 04:13:48
写在前面：这份解法是搬运，图片也是原回答评论区网友贡献，非本人原创：https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation. 展开全文
去ta的博客 赞 (150) 回复(12) 收起
头像 牛客题解官
发表于 2020-06-01 14:55:08
#描述 这是一篇针对初学者的题解，共用两种方法解决。 知识点：单链表，哈希，双指针 难度：二星 #题解 题目抽象：给定一个单链表，如果有环，返回环的入口结点，否则，返回nullptr ##方法一：哈希法 遍历单链表的每个结点 如果当前结点地址没有出现在set中，则存入set中 否则，出现在set 展开全文
去ta的博客 赞 (114) 回复(22) 收起
头像 中工升达预备毕业生
发表于 2019-10-01 14:05:12
看到这题时，无从下手...再看书时，书上逻辑思维真的太棒了，想问题的思路很nice！ 思路：1.判断链表中有环 -> 2.得到环中节点的数目 -> 3.找到环中的入口节点 /* public class ListNode { int val; ListNode next 展开全文
去ta的博客 赞 (54) 回复(11) 收起
头像 数据结构和算法
发表于 2021-06-30 17:03:14
之前讲过《NC4 判断链表中是否有环》 只需要判断是否有环即可，而今天这题如果有环还要找出环的入口，这题我们可以使用两种方式来解决 1，快慢指针解决 在前面我们提到过快慢指针，判断是否有环。如果有环，在来找环的入口。如果没环直接返回null即可，我们假设是有环的，那么会有两种情况，一种是O型，一种 展开全文
去ta的博客 赞 (47) 回复(2) 收起
头像 Dr_Wu_
发表于 2022-03-11 14:21:25
根据题目特点类似hash就行。 因为每个节点的值都是大于0的，小于10000，定义一个指针遍历，遍历到当前的就取负，如果遍历到一个节点他的值是负的就证明以前遍历过了，也就有环了，取个相反数返回就行 struct ListNode* EntryNodeOfLoop(struct 展开全文
去ta的博客 赞 (18) 回复(0) 收起
头像 ypqhappy
发表于 2021-08-20 21:55:34
set中存的是链表指针 class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { // 还是用哈希吧 unordered_set<ListNode*> set; 展开全文
去ta的博客 赞 (16) 回复(0) 收起
头像 designeer
发表于 2021-11-01 10:44:19
1，快慢指针解决 在前面我们提到过快慢指针，判断是否有环。如果有环，在来找环的入口。如果没环直接返回null即可，我们假设是有环的，那么会有两种情况，一种是O型，一种是6型，其实原理都一样，这里主要看一下6字型的环，他会有两种情况， 一种是环很大，如下图所示。 如果有 展开全文
去ta的博客 赞 (16) 回复(2) 收起
头像 静谧儒风
发表于 2022-01-25 18:32:12
链表中环的入口结点 题目： 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。 例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示： 可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。 输入描述： 输入分为2段，第一段是入环前的链表部分，第二 展开全文
去ta的博客 赞 (15) 回复(2) 收起
头像 夏日冬至
发表于 2021-10-05 19:13:16
使用HashSet类来解决 由于HashSet 是基于 HashMap 来实现的，是一个不允许有重复元素的集合。 因为将链表中所有的结点都遍历一遍，如果有环，那么在使用HashSet.contains()方法时，结果会出现true。 表示这个结点在集合中已经存过了，既这个结点就是 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 DreamYao-66
发表于 2021-10-03 13:47:26
/*function ListNode(x){ this.val = x; this.next = null; }*/ function EntryNodeOfLoop(pHead) { while(pHead !== null){ if(pHead.flag 展开全文
去ta的博客 赞 (11) 回复(4) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”