Skip to content

如何确定一个链表中有闭环

原文链接：如何确定一个链表中有闭环

利用两个指针p1,p2(每次分别增1和2)来进行判断

使用两个指针 ： slow和fast ， slow每次移动一位，fast每次移动两位，当发生以下条件之一时结束，时间复杂度为O(n)。

  • 首先一个终止的条件是指针p2遇到NULL节点.这说明不存在闭环
  • 另外一个条件式当两个指针相遇就终止,这说明有闭环

为什么有环的情况下二者一定会相遇呢？因为fast先进入环，在slow进入之后，如果把slow看作在前面，fast在后面每次循环都向slow靠近1，所以一定会相遇，而不会出现fast直接跳过slow的情况。

//判断是否有环  
bool isLoop(pNode pHead)  
{  
    pNode fast = pHead;  
    pNode slow = pHead;  
    //如果无环，则fast先走到终点  
    //当链表长度为奇数时，fast->Next为空  
    //当链表长度为偶数时，fast为空  
    while( fast != NULL && fast->next != NULL)  
    {  

        fast = fast->next->next;  
        slow = slow->next;  
        //如果有环，则fast会超过slow一圈  
        if(fast == slow)  
        {  
            break;  
        }  
    }  

    if(fast == NULL || fast->next == NULL  )  
        return false;  
    else
        return true;  
}

计算环的长度

如果有环两个指针相遇，那么在相遇后让fast不动，slow继续走，并开始计数，直到在两个指针重新相遇，这个长度就是环的长度。

int loopLength(pNode pHead)  
{  
    if(isLoop(pHead) == false)  
        return 0;  
    pNode fast = pHead;  
    pNode slow = pHead;  
    int length = 0;  
    bool begin = false;  
    bool agian = false;  
    while( fast != NULL && fast->next != NULL)  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
        //超两圈后停止计数，挑出循环  
        if(fast == slow && agian == true)  
            break;  
        //超一圈后开始计数  
        if(fast == slow && agian == false)  
        {             
            begin = true;  
            agian = true;  
        }  

        //计数  
        if(begin == true)  
            ++length;  

    }  
    return length;  
}

计算环的入口

假设链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，环的长度是L。如图所示 : 05171805-64db9f059a1641e7afaf3dd8223c4fe7.jpg

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c。我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。 我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

//求出环的入口点  
Node* findLoopEntrance(pNode pHead)  
{  
    pNode fast = pHead;  
    pNode slow = pHead;  
    while( fast != NULL && fast->next != NULL)  
    {  

        fast = fast->next->next;  
        slow = slow->next;  
        //如果有环，则fast会超过slow一圈  
        if(fast == slow)  
        {  
            break;  
        }  
    }  
    if(fast == NULL || fast->next == NULL)  
        return NULL;  
    slow = pHead;  
    while(slow != fast)  
    {  
        slow = slow->next;  
        fast = fast->next;  
    } 
    return slow;  
}

类似问题

查找单链表中倒数第n个节点

单向链表的特点是遍历到末尾后不能反向重数N个节点。因此必须在到达尾部的同时找到倒数第N个节点。通过一次遍历找到单链表中倒数第n个节点，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。 不管是顺数n个还是倒数n个，其实都是距离-标尺问题。标尺是一段距离可以用线段的两个端点来衡量，我们能够判断倒数第一个节点，因为他的next==NULL。如果我们用两个指针，并保持他们的距离为n，那么当这个线段的右端指向末尾节点时，左端节点就指向倒数第n个节点。

iNode * GetLastNnode(iNode * head, int n)
{
    iNode * pfirst=head;
    iNode *psecond=head;

    int counter;
    //第1步：建立标尺，移动pfirst N步
    for(counter=0; counter<n; counter++) 
    {
        if((NULL == pfirst)
        break; // 此时pfirst->next无意义
        pfirst=pfirst->next;
    }

    if(n != counter) //长度不够n，未找到倒数第n个节点
        return NULL;

    //第2步：保持距离让标尺向右移动，直到右端指向末尾，左端即结果
    while(pfirst!=NULL) 
    {
        pfirst=pfirst->next;
        psecond=psecond->next;
    }
    return psecond;
}


iNode * GetLastNnode ( iNode *head, int n)
{
    iNode * pfirst = head;
    iNode * psecond = NULL;//可能没有n个
    while( n-- > 0 && (pfirst!= NULL)
    {
        pfirst = pfirst ->next;
    }

    if(pfirst!= NULL)// 有n个节点
        psecond = head;

    while(pfirst!=NULL)
    {
         pfirst = pfirst ->next;
         psecond = psecond ->next;
    }
    return psecond; //只有一个出口，无论是否有n个节点，都能返回正确值
}

一次遍历单向链表找到中间节点

和上面的思路类似，设置2个指针，一个走2步时，另一个走1步。那么一个走到头时，另一个走到中间。

iNode * GetMiddleNode ( iNode *head )
{
    iNode *p1 = head;
    iNode *p2 = p1;
    while( p2 )
    {
        p2 = p2->next;
        if(p2)
        {
            p2 = p2->next;
            p1=p1->next;
        }
    }
    return p1;
}

参考