简便起见,用线性表(具体可由数组实现)保存节点指针。算法的时间复杂度为O(n^2)。
代码示例:
struct NodeType
{
int data
struct NodeType* next
}
int isloop(NodeType* p)
{
struct NodeType* list[100]/*保存节点指针的线性表,注意声明时需要保证足够大到存下链表的所有节点,也就是下标上限不小于节点数。*/
int n = 0/*记录 list 中保存的有效指针个数。*/
int i
while(p != NULL) /*存在直接后继节点。*/
{
for(i = 0i <n++i)
{
if(list[i] == p)/*存在重复节点。*/
return 1/*返回 1 ,说明是环形列表。*/
}
list[k++] = p/*记录节点。*/
p = p->next/*准备遍历下一个指针。*/
}
return 0/*遍历完整个链表,未发现重复节点,说明不是环形链表,返回 0 。*/
}
----
[原创回答团]
用两个指针来遍历这个单向链表,第一个指针p1,每次走一步;第二个指针p2,每次走两步;
当p2 指针追上p1的时候,就表明链表当中有环路了。
A.判断链表是否有环
设置两个指针p1和p2,初始值均指向链表头,p1每次向前走一步,而p2每次向前走两步。
如果链表有环,则p2先进入环里,而p1后进入环里,两个指针在环中必定相遇。
如果p1与p2没有相遇,p2遍历到链表的尾部,则表示链表没有环。
B.链表有环,确定环的入口点
设置p1指针指向链表头,p2指向相遇点,每次两个指针都是只走一步,两个指针必定相遇,
则相遇第一点为环入口点。
C.计算环长
在环的入口点设置一个指针和一个计数器,让这个指针在环里面走,每走一步,计数器就加1,
当这个指针回到环的入口点的时候,计数器的值就是环长。
例如:
int testLinkRing(Link *head)
{
Link *t1=head,*t2=headwhile( t1->next &&t2->next)
{
t1 = t1->nextif (NULL == (t2 = t2->next->next))return 0// 无环 if (t1 == t2)return 1
}
return 0
}