当前位置:网站首页>BM7 链表中环的入口结点
BM7 链表中环的入口结点
2022-08-10 21:49:00 【干饭小白】
审题:
如果给出的第二个链表不为空,则一定有环。
我们先把两种特殊情况搞定:
{1}、{} //无环,直接返回null
{}、{2} //有环,返回第二个链表任意节点
ok...好吧
我们看题目给的函数输入,只有一个参数,那么pHead是将两个链表已经链接好了。
好吧,是我想多了,看来这就是一个简单的找入环节点的问题。。。。
嘻嘻,见谅,见谅。。。。
至于为毛我要用这么通俗的话讲解,还不因为算法这个本来就比较抽象难懂,这样子表达会更容易理解和感同身受。。。呜呜,真是良苦用心,创作不易,点个关注吧,,,嘻嘻
如何判断有没有环:
通过快慢指针就ok
快指针,每次走两步,慢指针一次走一步(其实我感觉快指针只要比慢指针快就ok)
1.假设没有环,那么是不是可以理解为两个指针从同一个起点出发,沿着一条有尽头的路向前进军
2.假设有环,那么怎么理解呢?
假设有一天你偷偷出去上网,你老爸知道了,去网吧抓你。然后你跑到学校操场,停下来,你就对你爸说:“笨老头,抓不到我吧”。。。。
你和你爸同时在同一个起点出发(都是从你网吧的座位出发),你爸的速度是你的两倍,然后当你跑到操场,你沿着操场跑。你爸追你。是不是只要你爸速度比你快,就一定能够抓到你。怎么说呢,不晓得好理解波(如果有问题,可以私信)
如何找到入口节点:
根据XXX数学家,原谅我的无知,我只是知道这么个理论。。。。
fast和last相遇的点到入环节点 与 起点到入环节点距离相同
思路分析完了,上代码
别跟我说不会写代码,慢慢调呗。。。。可以借鉴,不可以照抄
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
ListNode *fast = nullptr;
ListNode *last = nullptr;
ListNode *p = nullptr;
if(pHead->next == nullptr || pHead->next->next == nullptr)
{
return p;
}
fast = pHead->next->next;
last = pHead->next;
while(1)
{
if(fast == nullptr || fast == last)
{
break;
}
if(fast->next != nullptr)
{
fast = fast->next->next;
}
else
{
fast = nullptr;
}
last = last->next;
}
if(fast == last)
{
p = pHead;
while(1)
{
if(p == last)
{
break;
}
p = p->next;
last = last->next;
}
}
return p;
}
};
日常吐槽:
写题目三分钟,写博客题解十年功
边栏推荐
猜你喜欢
Thread State 详解
ThreadLocal comprehensive analysis (1)
shell脚本
Shell编程之条件语句(二)
Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
艺术与科技的狂欢,阿那亚2022砂之盒沉浸艺术季
QT笔记——用VS + qt 生成dll 和 调用生成的dll
mmpose关键点(一):评价指标(PCK,OKS,mAP)
新一代网络安全防护体系的五个关键特征
使用 Cloudreve 搭建私有云盘
随机推荐
shell programming without interaction
port forwarding
关于 DataFrame: 处理时间
Black cat takes you to learn Makefile Part 11: When the header file a.h changes, how to recompile all the .c files that depend on the header file a.h
labelme-5.0.1版本编辑多边形闪退
ThreadLocal全面解析(一)
HighTec快捷键(Keys)设置位置
交换机和生成树知识点
GMT,UTC,CST,DST,RTC,NTP,SNTP,NITZ: 嵌入式的时间
2022.8.9 Mock Competition
力扣215题,数组中的第K个最大元素
特别的三杯鸡
Regular expression of shell programming and text processor
2022年8月的10篇论文推荐
《DevOps围炉夜话》- Pilot - CNCF开源DevOps项目DevStream简介 - feat. PMC成员胡涛
Service - DNS forward and reverse domain name resolution service
How to translate financial annual report, why choose a professional translation company?
Labelme-5.0.1 version edit polygon crash
过滤器
翻译科技论文,俄译中怎样效果好