脚本宝典收集整理的这篇文章主要介绍了算法大神对小码农说环形链表可以单独拿出来讲讲,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
我们剖析一下代码
bool hasCycle(struct ListNode *head) {
struct ListNode* fast = head,*slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}
结论:就上面fast和slow而言是一定相遇的
第一步:slow和fast,fast肯定是先进环,这时slow是fast入环前距离的一半。
第二步:随着slow进环,fast已经在环里走了一段了,走了 多少和环的大小有关系
第三步:我们这里假设slow进环的时候距离和fast是N
slow每次往前走1步,fast往前走两步,每追一次,判断一下相遇,结果为N-1,也就是说每追一次他们间的距离是一步一步的在减少,直到他们相遇
结论:fast走n步,n>2,不一定会相遇
这里分析一个slow走一步,fast走三步的交错与不交错的情况
他们之间的距离变化是每次是两两的减少,这也就意味着可能会交错
上面的奇偶问题也就又衍生出了N是他们的步差倍数就能相遇
如何求环的入口点
我们先直接放结论一个指针从相遇点开始走,一个指针从链表头开始走,他们会在环的入口点相遇
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode * fast = head,* slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(slow == fast)//相遇
{
//相遇节点
struct ListNode * meetNode = fast;
while(meetNode != head)
{
meetNode = meetNode->next;
head = head->next;
}
return meetNode;
}
}
return NULL;
}
以上是脚本宝典为你收集整理的算法大神对小码农说环形链表可以单独拿出来讲讲全部内容,希望文章能够帮你解决算法大神对小码农说环形链表可以单独拿出来讲讲所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。