PHP判断链表是否有环

发布网友 发布时间：2022-04-06 06:48

我来回答

共1个回答

热心网友 时间：2022-04-06 08:18

判断是否带环：用快慢指针。快指针每走两步，慢指针走一步，如果两者在某个点处相。

遇，则链表带环。

下边给出函数的实现代码：

typedef struct LinkNode{    DataType data;    struct LinkNode *next;}LinkNode,*pLinkNode;typedef struct LinkList{    LinkNode *pHead;}LinkList,*pLinkList;pLinkNode isCircle(pLinkList plist){    assert(plist);    if (NULL == plist->pHead)    {        printf("链表为空\n");        return NULL;    }    pLinkNode fast = plist->pHead;    pLinkNode slow = plist->pHead;    while (fast && fast->next)    {        fast = fast->next->next;        slow = slow->next;        if (fast == slow)            return fast;    }    return NULL;}

如果

如果链表带环，看下边的图：

代码：

pLinkNode firstCrossNode(pLinkList plist){    assert(plist);    if (NULL == plist->pHead)    {        printf("链表是空\n");        return NULL;    }    pLinkNode ret = isCircle(plist);    if (ret == NULL)    {        printf("链表不带环\n");        return NULL;    }    pLinkNode fast = plist->pHead;    pLinkNode slow = ret;    while (fast)    {        fast = fast->next;        slow = slow->next;        if (fast == slow)            return fast;    }}