链表--判断链表是否带环？若带环求环的长度？若带环求环的入口点？

本文主要是介绍链表--判断链表是否带环？若带环求环的长度？若带环求环的入口点？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

判断链表链表是否带环：
思路：给两个指针一快一慢，快的一次走两步，慢的一次走一步，如果两个指针最后相遇，则说明带环。
如果快指针到NULL，则说明没有环。

ListNode* IsHaveCircle(ListNode* pHead)
{assert(pHead);ListNode* pFast = pHead;ListNode* pSlow = pHead;//两个指针一个快一个慢，如果两个相遇了则有环while(pFast != NULL && pFast->Next != NULL){pFast = pFast->Next->Next;pSlow = pSlow->Next;if(pFast == pSlow)return pSlow;}return NULL;
}

求环的长度：
思路：
从交点给一指针，每次走一步，再走到这个位置的时候就停止。计数器就为环的长度

int CircleLength(ListNode* pHead)
{ListNode* pMeet = IsHaveCircle(pHead);assert(pMeet);int count = 0;ListNode* pCur = pMeet;//把环的入口点求出来，从此结点开始，每一次走一步，再次走到这个位置时则为长度。while(pMeet != pCur){pCur = pCur->Next;count++;}return count;
}

求环的入口点：
思路：

ListNode* FindLoopStart(ListNode* pHead)
{assert(pHead);ListNode* pMeet = IsHaveCircle(pHead);assert(pMeet);ListNode* pCur = pHead;//由上图，从头到环入口的距离等于交点到环入口的距离。//所以当头和环内交点一步一步向后走，两点重合的哪一点即为入口点while(pMeet != pCur){pMeet = pMeet->Next;pCur= pCur->Next;}return Cur;
}

这篇关于链表--判断链表是否带环？若带环求环的长度？若带环求环的入口点？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---