面试经典算法-floyd判环(圈)算法

综合技术 CSDN博客 (源链)

floyd(Floyd cycle detection)

问题:如何检测一个链表是否有环,如果有,那么如何确定环的起点?如何确定环的长度?

  • 时间复杂度:O(n) (高效率)
  • 空间复杂度:O(1)

此算法又成为龟兔赛跑算法,基本思想是:

好比两个人在赛跑,A的速度快,B的速度慢,经过一定时间后,A总是会和B相遇,且相遇时A跑过的总距离减去B跑过的总距离一定是圈长的n倍(初中数学题……)。

弗洛伊德(Floyd )使用了两个指针,一个慢指针(龟)每次前进一步,快指针(兔)指针每次前进两步(两步或多步效果是等价的,只要一个比另一个快就行。但是如果移动步数增加,算法的复杂度可能增加)。如果两者在链表头以外(不包含开始情况)的某一点相遇(即相等)了,那么说明链表有环,否则,如果(快指针)到达了链表的结尾(如果存在结尾,肯定无环),那么说明没环。

环的检测从上面的解释理解起来应该没有问题。接下来我们来看一下如何确定环的起点,这也是Floyd解法的第二部分。方法是将慢指针(或快指针)移到链表起点,然后两者同时移动,每次移动一步,那么两者相遇的地方就是环的起点。

下面给出论证过程:

假设一个链表是下面这样的:

设环长为n,非环形部分长度为m,当第一次相遇时显然slow指针行走了 m+A*n+k(A表示slow行走了A圈。附:A*n 是因为如果环够大,则他们的相遇需要经过好几环才相遇)。fast行走了 m+B*n+k。

上面我们说了slow每次行走一步,fast每次行走两步,则在同一时间,fast行走的路程是slow的两倍。假设slow行走的路程为S,则fast行走的路程为2S。

用fast减去slow可得:

S=(B-A)*n

很显然这意味着当slow和fast相遇时他们走过的路程都为圈长的倍数。

接下来,将slow移动到起点位置,如下图:

然后每次两个指针都只移动一步,当slow移动了m,即到达了环的起点位置,此时fast总共移动了 2S+m。 考虑到S为环长的倍数,可以理解为:fast先从链表起点出发,经过了m到达环的起点,然后绕着环移动了几圈,最终又到达环的起点,值为2S+m。所以fast最终必定处在环的起点位置。即两者相遇点即为环的起点位置。

算法如下(Java):

public ListNode findBeginLoop(ListNode head){

ListNode slowPtr=head;
ListNode fastPtr=head;
boolean loopExists=false;

if(head=null){return 0;}

while(slowPtr.getNext()!=null && fastPtr.getNext().getNext()!=nulll){
 slowPtr=slowPtr.getNext();
 fastPtr=fastPtr.getNext().getNext();
 if(slowPtr==fastPtr){
    loopExists=true;
    break;
    }
  }
  if(loopExists){  //环存在
    slowPtr=head;
    while(slowPtr!=fastPtr){
        slowPtr=slowPtr.getNext();
        fastPtr=fastPtr.getNext();
    }
    return slowPtr;
  } 
  return null; //环不存在
}

如果要求环的长度,可以这样做:

当两者相遇之后,固定一个指针,让另一个指针行走一圈,使用count计数,如果两个指针相等(即相遇),则count即为环的长度。

csdn地址: http://blog.csdn.net/u012534831

github地址: https://github.com/qht1003077897

个人博客地址: https://qht1003077897.github.io/

QQ:1003077897

您可能感兴趣的

面试题57. 删除链表中重复的结点 面试题57. 删除链表中重复的结点 题目描述 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5 思路: 定义三个...
Algorithms and Data Structures in JavaScript JavaScript Algorithms and Data Structures This repository contains JavaScript based examples of many popular algorithms and data structures. Ea...
每周一算法2017.11.24 Longest Harmonious Subsequence We define a harmonious array is an array where the difference between its maximum value and its minimum value is exac...
C语言/C++编程学习数据结构与算法:通俗易懂讲解:位序... C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到输出(或实现过程(事务)控制)。 C++,首要考虑的是如何构造一个对象模型,让这个模型能够契合与之对...
Multidimensional algorithms and iteration Starting with release 0.4, Julia makes it easy to write elegant and efficient multidimensional algorithms. The new capabilities rest on two foundatio...
CSDN博客责编内容来自:CSDN博客 (源链) | 更多关于

阅读提示:酷辣虫无法对本内容的真实性提供任何保证,请自行验证并承担相关的风险与后果!
本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 面试经典算法-floyd判环(圈)算法



专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录