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

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

首先，有環(huán)的鏈表應該長這樣。

?

正常的單向鏈表最后一個結點的指針域應該是NULL，表示后面沒有結點。

?

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

?


? ? 如何判斷鏈表是否有環(huán)，其中一個比較常見的方法就是，兩個指針，經(jīng)常把他們稱作快慢指針，慢的指針每次走一步，快的指針每次走兩步，如果鏈表沒環(huán)，快的指針肯定最先達到終點；如果鏈表有環(huá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;
}

?

當快指針和慢指針相遇的時候，再定義一個指針指開頭。該指針和慢指針同時向后走。兩個指針相遇的時候，就是環(huá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)開始的結點*/
                }
            }
        }
    }


    return 0;
}

?

　　審核編輯：湯梓紅

?