当前位置:C++技术网 > 资讯 > 数据结构笔记分享:41 如何判断链表可能有环

数据结构笔记分享:41 如何判断链表可能有环

更新时间:2016-02-05 20:05:26浏览次数:1+次

  当然我们这里说的环是三个元素组成的环形所以这里就有这样的办法:

  设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:


bool IsExitsLoop(slist *head)  
{  
    slist *slow = head, *fast = head;  
  
    while ( fast && fast->next )   
    {  
        slow = slow->next;  
        fast = fast->next->next;  
        if ( slow == fast ) break;  
    }  
  
    return !(fast == NULL || fast->next == NULL);  
}  
 其实听起来问题很复杂,感觉无从下手,但是程序运行起来无非弄出两个循环遍历,假如遇到环形,必定快的那个回合慢的相遇,这时候问题就解决了。