牛客 剑指Offer 单链表判断是否有环 以及找出环的入口点
程序员文章站
2022-07-03 17:54:21
牛客 剑指Offer 单链表判断是否有环 以及找出环的入口点。...
题目:
给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。
解析:
代码:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode*slow=pHead;
ListNode*fast=pHead;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
fast=pHead;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
}
return NULL;
}
};
基本思路:
我的解析里面写的还是比较清楚的。这里简单说明一下。解析里面数学证明了如果有环的话,快慢指针一定会相遇的。后面还证明了在相遇之后,把fast指针拿到链表头,slow从相遇点向后移动,现在,二者都是每次移动一个位置。二者的初次相遇点就是链表的环的入口。
谢谢阅读!
本文地址:https://blog.csdn.net/weixin_40007143/article/details/107297812
上一篇: 颜色空间:RGB,CMY,HSV,HSL,Lab,YUV详解
下一篇: 荐 牛客算法周周练14题解