(資料圖片)

如何判斷鏈表是否有環？首先，有環的鏈表應該長這樣。 正常的單向鏈表最后一個結點的指針域應該是NULL，表示后面沒有結點。 但是如果把它改成前面某個結點的地址，就會變成這個樣子，這樣的鏈表就叫有環的鏈表。 如何判斷鏈表是否有環，其中一個比較常見的方法就是，兩個指針，經常把他們稱作快慢指針，慢的指針每次走一步，快的指針每次走兩步，如果鏈表沒環，快的指針肯定最先達到終點；如果鏈表有環，那么兩個指針遲早相遇。 代碼也極其簡單：

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;}

當快指針和慢指針相遇的時候，再定義一個指針指開頭。該指針和慢指針同時向后走。兩個指針相遇的時候，就是環開始的結點。

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)                {                    /*環開始的結點*/                }            }        }    }    return 0;}

審核編輯：湯梓紅