« XML初探(一) | Main | 按单词反转字符串 »

判断链表是否存在环

问题:判断一个链表是否存在环,例如下面这个链表就存在一个环:
例如N1->N2->N3->N4->N5->N2就是一个有环的链表,环的开始结点是N5

这里有一个比较简单的解法。设置两个指针p1,p2。每次循环p1向前走一步,p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。

struct link {
    int data;
    link* next;
};

bool IsLoop(link* head)
{
    link* p1=head, *p2 = head;
	if (head ==NULL || head->next ==NULL) {
		return false;
	}
    do{
        p1= p1->next;
        p2 = p2->next->next;
    } while(p2 && p2->next && p1!=p2);     
	if(p1 == p2)
		return true;
	else
		return false;
}

TrackBack

TrackBack URL for this entry:
http://www.zhuxinquan.com/mt_zxq/mt-tb.cgi/79

Post a comment