当前位置:网站首页>第一讲:链表中环的入口结点
第一讲:链表中环的入口结点
2022-07-07 22:21:00 【奋斗吧!骚年!】
题目:链表中环的入口结点
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出null。
数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。
样例
给定如上所示的链表:
[1, 2, 3, 4, 5, 6]
2
注意,这里的2表示编号是2的节点,节点编号从0开始。所以编号是2的节点就是val等于3的节点。
则输出环的入口节点3.
题目解析:
方法一:哈希表
我们可以使用unordered_set,来保存节点指针,如果发现有相同的指针(set的大小不变),则表示是入口节点
方法二:快慢指针
原理:快指针每次走两步,慢指针每次走一步,如果有环则一定会相遇
如图,假设慢指针从a走到b最后与快指针相遇于c,如果慢指针返回到b点,则快指针会返回到d点(因为会多走y步)
那么我们可以发现当慢指针走到b点,那么快指针就会走到d点(因为回退得出的),那么x+y就会是圈的整数倍(其实可能快指针已经在圈里走过很多圈了,但是这不影响,相当于取余操作)
最后我们将慢指针移到起点,两个指针走同样的步数,则就会在入口相遇(因为快指针已经走了y步,再走x步肯定会在b点,而慢指针走x步也会在b点)
执行次数:x+y+2x+2y+2x=5x+3y(因为x+y小于总长度,所以时间复杂度0(n))
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
if(!head)return NULL;
set<ListNode *> s;
while(head->next)
{
int size=s.size();
s.insert(head);
if(size==s.size())return head;
head=head->next;
}
return NULL;
}
};
边栏推荐
- 52歲的周鴻禕,還年輕嗎?
- DNS 系列(一):为什么更新了 DNS 记录不生效?
- QT and OpenGL: load 3D models using the open asset import library (assimp)
- 腾讯安全发布《BOT管理白皮书》|解读BOT攻击,探索防护之道
- Cmake learning notes (1) compile single source programs with cmake
- Go learning notes (1) environment installation and hello world
- 应用实践 | 数仓体系效率全面提升!同程数科基于 Apache Doris 的数据仓库建设
- [programming problem] [scratch Level 2] March 2019 draw a square spiral
- Solution to prompt configure: error: curses library not found when configuring and installing crosstool ng tool
- Problems faced when connecting to sqlserver after downloading (I)
猜你喜欢
Installation and configuration of sublime Text3
如何衡量产品是否“刚需、高频、痛点”
2022-07-07:原本数组中都是大于0、小于等于k的数字,是一个单调不减的数组, 其中可能有相等的数字,总体趋势是递增的。 但是其中有些位置的数被替换成了0,我们需要求出所有的把0替换的方案数量:
[basis of recommendation system] sampling and construction of positive and negative samples
Fully automated processing of monthly card shortage data and output of card shortage personnel information
CoinDesk评波场去中心化进程:让人们看到互联网的未来
When creating body middleware, express Is there any difference between setting extended to true and false in urlencoded?
浪潮云溪分布式数据库 Tracing(二)—— 源码解析
Play sonar
用語雀寫文章了,功能真心强大!
随机推荐
Reptile practice (VIII): reptile expression pack
Single machine high concurrency model design
数据库查询——第几高的数据?
RPA云电脑,让RPA开箱即用算力无限?
Basic learning of SQL Server -- creating databases and tables with the mouse
Zhou Hongqi, 52 ans, est - il encore jeune?
[question de programmation] [scratch niveau 2] oiseaux volants en décembre 2019
某马旅游网站开发(登录注册退出功能的实现)
How to insert highlighted code blocks in WPS and word
面试题详解:用Redis实现分布式锁的血泪史
1293_FreeRTOS中xTaskResumeAll()接口的实现分析
ROS from entry to mastery (IX) initial experience of visual simulation: turtlebot3
Robomaster visual tutorial (10) target prediction
The difference between -s and -d when downloading packages using NPM
Common selectors are
手写一个模拟的ReentrantLock
Notice on organizing the second round of the Southwest Division (Sichuan) of the 2021-2022 National Youth electronic information intelligent innovation competition
智慧监管入场,美团等互联网服务平台何去何从
Opengl3.3 mouse picking up objects
SQL knowledge summary 004: Postgres terminal command summary