如何判斷鏈表是否有環(huán)？

首先，有環(huán)的鏈表應(yīng)該長(zhǎng)這樣。

?

正常的單向鏈表最后一個(gè)結(jié)點(diǎn)的指針域應(yīng)該是NULL，表示后面沒(méi)有結(jié)點(diǎn)。

?

但是如果把它改成前面某個(gè)結(jié)點(diǎn)的地址，就會(huì)變成這個(gè)樣子，這樣的鏈表就叫有環(huán)的鏈表。

?


? ? 如何判斷鏈表是否有環(huán)，其中一個(gè)比較常見(jiàn)的方法就是，兩個(gè)指針，經(jīng)常把他們稱作快慢指針，慢的指針每次走一步，快的指針每次走兩步，如果鏈表沒(méi)環(huán)，快的指針肯定最先達(dá)到終點(diǎn)；如果鏈表有環(huán)，那么兩個(gè)指針遲早相遇。


?

代碼也極其簡(jiǎn)單：
?

int is_cross(Node *head)
{
    if (NULL == head)
        return 0;


    Node *fast = head;
    Node *slow = head;


    while (fast && slow)
    {   
        if (fast->next && fast->next->next)
            fast = fast->next->next;
        else
            break;


        if (slow->next)
            slow = slow->next;
        else
            break;


        if (fast == slow)
            return 1;
    }


    return 0;
}

?

當(dāng)快指針和慢指針相遇的時(shí)候，再定義一個(gè)指針指開(kāi)頭。該指針和慢指針同時(shí)向后走。兩個(gè)指針相遇的時(shí)候，就是環(huán)開(kāi)始的結(jié)點(diǎn)。
?

?

int is_cross(Node *head)
{
    if (NULL == head)
        return 0;


    Node *fast = head;
    Node *slow = head;


    while (fast && slow)
    {
        if (fast->next && fast->next->next)
            fast = fast->next->next;
        else
            break;


        if (slow->next)
            slow = slow->next;
        else
            break;


        if (fast == slow)
        {
            Node *p = head;
            while (p != slow)
            {
                p = p->next;
                slow = slow->next;


                if (p == slow)
                {
                    /*環(huán)開(kāi)始的結(jié)點(diǎn)*/
                }
            }
        }
    }


    return 0;
}

?

　　審核編輯：湯梓紅

?