﻿ 判斷單鏈表是否有環？如何找到環的“起始”點？如何知道環的長度？_電腦知識網

# 判斷單鏈表是否有環？如何找到環的“起始”點？如何知道環的長度？

2022-06-13   來源: 數據結構

{
while (secondNext != null &#;&#; secondNextNext != null)
{
second = secondNextNext;
first = firstNext;
if (second == first)
return true;
}
return false;
}

{
int length = ;
while (currNext != point)
{
length++;
curr = currNext;
}
return length;
}

{
int length = ;
while (curr != point)
{
length++;
curr = currNext;
}
return length;
}

{
//get the point in the circle
bool result = JudgeCircleExists(head ref p);
if (!result) return null;
int M = ;
while (curr != p)
{
M++;
curr = currNext;
}
//circle length
int N = ;
while (curr != p)
{
N++;
curr = currNext;
}
//recover curr &#; curr
curr = pNext;
//make links have the same distance to the intersect
if (M > N)
{
for (int i = ; i < M &#; N; i++)
curr = currNext;
}
else if (M < N)
{
for (int i = 0; i < N – M; i++)
curr2 = curr2.Next;
}
//goto the intersect
while (curr1 != p)
{
if (curr1 == curr2)
{
return curr1;
}
curr1 = curr1.Next;
curr2 = curr2.Next;
}
return null;
}

From:http://tw.wingwit.com/Article/program/sjjg/201405/30932.html
• 上一篇文章：

• 下一篇文章：