|
算法思想
先分析是否有环为此我们建立两个指针从header一起向前跑一个步长为一个步长为用while（直到步长的跑到结尾）检查两个指针是否相等直到找到为止
static bool JudgeCircleExists(Link head)
{
Link first = head; // step each time
Link second = head; // steps each time
while (secondNext != null &#;&#; secondNextNext != null)
{
second = secondNextNext;
first = firstNext;
if (second == first)
return true;
}
return false;
} 那又如何知道环的长度呢？
根据上面的算法在返回true的地方也就是个指针相遇处这个位置的节点P肯定位于环上我们从这个节点开始先前走转了一圈肯定能回来
static int GetCircleLength(Link point)
{
int length = ;
Link curr = point;
while (currNext != point)
{
length++;
curr = currNext;
}
return length;
} 继续我们的讨论如何找到环的起始点呢？
延续上面的思路我们仍然在返回true的地方P计算一下从有环单链表的表头head到P点的距离
static int GetLengthFromHeadToPoint(Link head Link point)
{
int length = ;
Link curr = head;
while (curr != point)
{
length++;
curr = currNext;
}
return length;
} 如果我们把环从P点切开（当然并不是真的切那就破坏原来的数据结构了）那么问题就转化为计算两个相交单链表的交点（第题）
一个单链表是从P点出发到达P（一个回圈）距离M另一个单链表从有环单链表的表头head出发到达P距离N
我们可以参考第题的GetIntersect方法并稍作修改
private static Link FindIntersect(Link head)
{
Link p = null;
//get the point in the circle
bool result = JudgeCircleExists(head ref p);
if (!result) return null;
Link curr = headNext;
Link curr = pNext;
//length from head to p
int M = ;
while (curr != p)
{
M++;
curr = currNext;
}
//circle length
int N = ;
while (curr != p)
{
N++;
curr = currNext;
}
//recover curr &#; curr
curr = headNext;
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;
} |
