# 链表带环问题

1、判断链表是否带环

``````PNode HasCircle(PNode pHead)// 判断单链表是否带环
{
//快慢指针

while (pFast && pSlow){
pFast = pFast->pNext->pNext;
pSlow = pSlow->pNext;
if (pFast == pSlow)
return pSlow;
}
return NULL;
}``````

2、求环的长度

``````size_t GetCircleLen(PNode pHead)// 求环的长度
{
PNode pCur = NULL;
size_t len = 0;
if (pMeetNode == NULL)
return 0;
pCur = pMeetNode;
while (pCur->pNext!= pMeetNode){
len++;
pCur = pCur->pNext;
}
return len;
}``````

3、求环的入口点

F = 2S
S=x+d
F=2 ( x + d ) = x + d + ny

``````
PNode GetEnterNode(PNode pHead, PNode pMeetNode)// 求环的入口点
{
PNode pM = pMeetNode;
if (pH == NULL || pM == NULL)
return NULL;
//到这步说明链表一定有环
while (pH != pM){
pH = pH->pNext;
pM = pM->pNext;
}
return pM;
}``````

4、判断两链表是否相交（假设链表不带环）

``````//判断两个不带环链表是否相交(假设链表不带环)
{

while (pTail1)
pTail1 = pTail1->pNext;

while (pTail2)
pTail2 = pTail2->pNext;

return pTail1 == pTail2;
}``````

5、求交点

``````
{
size_t size1 = 0;
size_t size2 = 0;
int div = 0;

return NULL;

return 0;

while (pCur1)
{
size1++;
pCur1 = pCur1->pNext;
}

while (pCur2)
{
size2++;
pCur2 = pCur1->pNext;
}

div = size1 - size2;
if (div > 0)
{
while (div--)
pCur1 = pCur1->pNext;
}
else
{
while (div++)
pCur2 = pCur2->pNext;
}

while (pCur1 != pCur2)
{
pCur1 = pCur1->pNext;
pCur2 = pCur2->pNext;
}
return pCur1;
}
``````