TOP

判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度?
2014-11-24 02:23:10 】 浏览:1089
Tags:判断 单链表 是否 如何 找到 起始 ”点 知道 长度

算法思想:
先分析是否有环。为此我们建立两个指针,从header一起向前跑,一个步长为1,一个步长为2,用while(直到步长2的跑到结尾)检查两个指针是否相等,直到找到为止。
static bool JudgeCircleExists(Link head)
{
Link first = head; //1 step each time
Link second = head; //2 steps each time
while (second.Next != null && second.Next.Next != null)
{
second = second.Next.Next;
first = first.Next;
if (second == first)
return true;
}
return false;
}


那又如何知道环的长度呢?
根据上面的算法,在返回true的地方,也就是2个指针相遇处,这个位置的节点P肯定位于环上。我们从这个节点开始先前走,转了一圈肯定能回来:
static int GetCircleLength(Link point)
{
int length = 1;
Link curr = point;
while (curr.Next != point)
{
length++;
curr = curr.Next;
}
return length;
}


继续我们的讨论,如何找到环的“起始”点呢?
延续上面的思路,我们仍然在返回true的地方P,计算一下从有环单链表的表头head到P点的距离
static int GetLengthFromHeadToPoint(Link head, Link point)
{
int length = 1;
Link curr = head;
while (curr != point)
{
length++;
curr = curr.Next;
}
return length;
}


如果我们把环从P点“切开”(当然并不是真的切,那就破坏原来的数据结构了),那么问题就转化为计算两个相交“单链表”的交点(第10题):
一个单链表是从P点出发,到达P(一个回圈),距离M;另一个单链表从有环单链表的表头head出发,到达P,距离N。
我们可以参考第10题的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 curr1 = head.Next;
Link curr2 = p.Next;
//length from head to p
int M = 1;
while (curr1 != p)
{
M++;
curr1 = curr1.Next;
}
//circle length
int N = 1;
while (curr2 != p)
{
N++;
curr2 = curr2.Next;
}
//recover curr1 & curr2
curr1 = head.Next;
curr2 = p.Next;
//make 2 links have the same distance to the intersect
if (M > N)
{
for (int i = 0; i < M – N; i++)
curr1 = curr1.Next;
}
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;
}



判断单链表是否有环?如何找到环的“起始”点?如何知道环的长度? https://www.cppentry.com/bencandy.php?fid=43&id=35975

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Oracle DBA笔试题 下一篇atexit函数做什么的

kafka-
kafka   Partit
解决android studio
Kafka史上最详细原理
Error while fetchin
【Kafka】安装与快速
    &
flume读取日志数据写
Authentication plug
Flume 自定义source
flume   三大核
ICC副本>>>
愚公移山  
Hbase架构   Hb
5 hbase-shell + &
Hbase   MapRed
MetaException(messa
Exception in thread
HIVE metastore Dupl
-->