//判斷鏈表是否有環


int HasCircle(Node* pHead)
{
Node* low=pHead;
Node* fast=pHead;
? ? while(fast != NULL && fast->next != NULL)
? ? {
? ? ? ? low=low->next;
? ? ? ? fast=fast->next->next;
? ? ? ? if(low==fast)?
return 1;
}
? ? return 0;
}

時間復雜度：O(1)

//求環中快慢指針相遇節點
Node* HasCircle(Node* pHead)
{
Node* low=pHead;
Node* fast=pHead;
? ? if(pHead==NULL)?
return NULL;
? ? while(fast != NULL && fast->next != NULL)
? ? {
? ? ? ? low=low->next;
? ? ? ? fast=fast->next->next;
? ? ? ? if(low==fast)?
return low;
}
? ? return NULL;
}
//求環長度
int GetCircleLen(Node* pMeetNode)
{
Node* Node = pMeetNode->next;


int lenght = 1;
while(Node != pMeetNode )
{
lenght++;
Node = Node->next;
}
return lenght;
}

時間復雜度：O(1)

//求環的入口
Node* GetEnterNode(Node* pHead, Node* pMeetNode)
{
Node* start = pHead;
if(pHead == NULL)
return NULL;

while(start != pMeetNode)
{
start = start->next;
pMeetNode = pMeetNode->next;
}
return start;
}

時間復雜度：O(1)

總結

以上是生活随笔為你收集整理的数据结构：单链表操作之如何判断链表是否带环及相关操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。