本文主要是介绍牛客网剑指offer刷题练习之链表中环的入口结点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
✅作者简介:C/C++领域新星创作者,为C++和java奋斗中
✨个人社区:微凉秋意社区
🔥系列专栏:剑指offer刷题
📃推荐一款模拟面试、刷题神器👉注册免费刷题
🔥前言
今天分享用C++做算法题的经验,题目来自于牛客网《剑指offer》专栏里的一道中等难度的链表题,用到了快慢指针的思想。当然除了快慢指针也用到了其他的数学思想,感兴趣的小伙伴快来看看吧!
活动地址:CSDN21天学习挑战赛
文章目录
- 链表中环的入口结点问题
- 一、题目描述
- 二、题目解析
- 1、解题思路
- 2、证明结论
- 三、代码实现与解释
- 1、题目源码
- 2、重要代码解释
链表中环的入口结点问题
一、题目描述
输出示例:
二、题目解析
1、解题思路
解题思路分为两部分:
- 遇到链表中环的问题优先考虑双指针里的快慢指针,快指针就是一次走两个路径,慢指针则只走一个路径,只要快慢指针相遇就返回该结点位置。只要链表中存在环,那么快慢指针必定会相遇。
- 快指针从头开始,慢指针从相遇点开始,二者同时开始走,再次相遇时的位置必定是环的入口处。
2、证明结论
- 必定会相遇
设置快慢指针
fast
和low
,fast每次走两步,low每次走一步。假如有环,两者一定会相遇(因为low一旦进环,可看作fast在后面追赶low的过程,每次两者都接近一步,最后一定能追上)。
- 必定是环的入口处
链表头到环入口长度 ——
a
环入口到相遇点长度为——b
相遇点到环入口长度为——c
当fast与slow相遇时,fast走过的距离为a + k(b + c) + b,而slow走过的距离为a + b,因为fast是slow速度的两倍,则有a+k(b + c)+b = 2*(a+b),化简得出a=b(k-1)+kc
;此时slow节点在相遇点,由表达式可以看出当k为一时,a=c,那么我们让快指针从起点开始走,刚好可以让快慢指针在环入口处相遇。(k是fast走过的环数)
三、代码实现与解释
1、题目源码
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* EntryNodeOfLoop(ListNode* pHead) {ListNode* slow=flpointer(pHead);if(slow==NULL)return NULL;ListNode* fast=pHead;while(fast!=slow){fast=fast->next;slow=slow->next;}return slow;}ListNode* flpointer(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(slow==fast)return slow;}return NULL;}
};
2、重要代码解释
ListNode* flpointer(ListNode* head)
这个函数的作用是找到快慢指针的相遇点。先考虑并处理链表为空的情况,然后定义快慢指针,当快指针对应的结点以及相邻结点不为空时让快指针走两步,慢指针走一步,直到二者相等返回结点位置。
ListNode* EntryNodeOfLoop(ListNode* pHead)
这个函数的作用就是调用上面flpointer函数并解决问题。当存在快慢指针相等情况时,让快指针从头开始走,与相遇时同时进行,只要相遇就返回结点,这个结点位置就是环入口。
写在最后
有关链表环的题目大都是和双指针有关,认真的做一道题比盲目刷几十道收获要大得多,勤做笔记,善于用思考才会变强!让我们一起刷题,提升自己吧!!!
这篇关于牛客网剑指offer刷题练习之链表中环的入口结点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!