判断单链表是否有环

算法思路： 指针p1和p2的起始值均为链表的表头，指针p1每次走一步，指针p2每次走两步。如果链表存在环，则当p1和p2都进入环时，p2会“追上”p1，因为每次行走，p2和p1的距离都缩短了1.

 

//visual studio 2012 下编译通过
#include <stdio.h>
struct node{
	int val;
	node* next; 
	node(int val, node* next){
		this->val = val;
		this->next = next;
	}
};
/*
 * @brief 判断以head节点开头的单链表是否存在环, 时间复杂度是O(n),空间复杂度是O(1)
 * @param node* head 链表的起始节点
 */
bool hasCircle(node* head){
	node *p1, *p2;
	p1 = p2 = head;
	while(true){
		if(p1 == NULL || p2 == NULL) return false; 
		p1 = p1->next; 
		p2 = p2->next; 
		if(p2 == NULL) return false; 
		p2 = p2->next; 
		if(p1 == p2) return true; 
	}
	return true; 
}


int main(){
	//输入和输出重定向
	freopen("in.txt","r", stdin);
	freopen("out.txt", "w", stdout);
	node *p1 = new node(1, NULL),
		 *p2 = new node(2, NULL),
		 *p3 = new node(3, NULL),
		 *p4 = new node(4, NULL);
	/*
	 *case one 
	 */
	p1->next = p2; 
	p2->next = p3; 
	p3->next = p4; 
	p4->next = p2;
	if(hasCircle(p1)){
		fprintf(stdout, "result of case one is yes \n");
	}else{
		fprintf(stdout, "result of case one is no \n");
	}
	
	/*
	 *case two 
	 */
	p1->next = p2; 
	p2->next = p3; 
	p3->next = p4; 
	p4->next = NULL;
	if(hasCircle(p1)){
		fprintf(stdout, "result of case two is yes \n");
	}else{
		fprintf(stdout, "result of case two is no \n");
	}

	/*
	 *case three 
	 */
	p1->next = p2; 
	p2->next = p3; 
	p3->next = p4; 
	p4->next = p1;
	if(hasCircle(p1)){
		fprintf(stdout, "result of case three is yes \n");
	}else{
		fprintf(stdout, "result of case three is no \n");
	}

}