- 注册时间
- 2011-3-6
- 最后登录
- 1970-1-1
该用户从未签到
|
定义两个指针;
第一个指针向前跑,另一个指针跑第一个指针跑过的,如果发现相等,则说明存在循环
我的设计是用一个变量记录第一个指针跑过的个数 然后根据这个数决定第二个指针跑几次
如果发现相等就循环
代码:
//pEnd跑pFirst跑过的 如果pEnd在跑的过程中发现与pFirst相同的即为循环链表
int FindLoop(PNODE head)
{
PNODE pFirst = 0;
PNODE pEnd = pFirst = head;
ULONG count = 0;
while( pFirst != NULL && pEnd != NULL && pFirst->next != NULL )
{
pFirst = pFirst->next;
pEnd = head;
count ++;
for(ULONG i=0;i<count;i++)
{
if(pEnd == pFirst)
{
return 1;
}
pEnd = pEnd->next;
}
}
return 0;
}[/code]
这个代码可以改为返回节点,得到循环点
也可以改改 第二个循环条件改为两个指针不相等
代码:
有一些改变,pf用来跑全程
NODE *FindLoop_Ex_Ex(NODE *head)
{
NODE *pc = head;
NODE *pf = NULL;
if (!pc)
return NULL;
while (pc)
{
pf = head;
while(pf && pf != pc)
{
//当前结点的下一个结点是它前面的某个结点或者是它自己,则为循环处
if (pc->next == pf || pc->next == pc)
return pc->next;
pf = pf->next;
}
pc = pc->next;
}
return NULL;
}[/code]
如果不需要知道循环点的话,可以使用步长法:
原理:如何判断是否有环?如果有两个头结点指针,一个走的快,一个走的慢,那么若干步以后,快的指针总会超过慢的指针一圈。
int FindLoop_Ex(NODE *head)
{
NODE *p = NULL;
NODE *q = NULL;
if (head == NULL)
return 0;
p = head;
q = head->next;
while (p != NULL && q != NULL && q->next != NULL && p != q) //p != 关键判断 等同入在下面代码中写入 if(p == q)
{
p = p->next;
q = q->next->next;
}
if (p == q)
return 1;
else
return 0;
}[/code]
如何计算环的长度?第一次相遇(超一圈)时开始计数,第二次相遇时停止计数。
根据步长法来得到
int GetLoopLen(PNODE head)
{
NODE *p = NULL;
NODE *q = NULL;
int len = 0;
bool ok = false;
if (head == NULL)
return 0;
p = head;
q = head->next;
while (p != NULL && q != NULL && q->next != NULL)
{
p = p->next;
q = q->next->next;
if(p == q)
{
if(ok)
{
ok = false;
break;
}
p = head;
q = head->next;
ok = true;
}
if(ok)
len++;
}
return len;
}[/code] |
|