(资料图片)

如何判断链表是否有环？首先，有环的链表应该长这样。 正常的单向链表最后一个结点的指针域应该是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;}

审核编辑：汤梓红