链表是否有环的两种判断方法

判断单链表是否有环

假设有一个含环链表：1-2-3-4-5-6-3（6又连接到3，形成一个环）

1. 使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。当p从6走到3时，用了6步；此时q从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。而且**可以锁定环的位置，就是q的步数+1**

2. 使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环。虽然无法锁定环的位置，**但是占用空间和时间少。**这就是之前说的快慢链表里面的快慢指针。

实现:

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXLEN = 6;

struct Node{
	int val;
	Node *next;
};


int  IfLoop(Node *head){
	Node * cur1 = head;
	int pos1 = 0;
	while(cur1){
		Node * cur2 = head;
		int pos2 = 0;
		pos1++;
		while(cur2){
			pos2++;
			if(cur2==cur1){
				if(pos1==pos2)
					break;
				else
					return pos2;
			}
			cur2 = cur2->next;
		}
		cur1 = cur1->next;
	}
	return -1;
}

bool IfLoop_2(Node *head){
	Node * p = head;
	Node * q = head;
	while(p && q){
		p = p->next;
		q = q->next;
		if(q)
			q = q->next;
		if (p && p==q)
			return true;
	}
	return false;
}

int main(){
	Node *head = new Node;
	head->val = 0;
	
	Node *s = new Node; 
	
	Node *p = new Node;
	head->next = p;
	
	for(int i=0;i<MAXLEN;++i){
		p->val = i+1;
		p->next = s; 
		p =s;
		s = new Node;
	}
	
	p->next = head->next->next;
	 
	cout<<"位置在："<<IfLoop(head)<<"，如果位置是-1，则不存在"<<endl;
		
	return 0;
	
}

欢迎进一步交流本博文相关内容：

博客园地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信进行交流 : xiaochiyijiu@163.com

欢迎转载 , 但请指明出处  :  )

后话：估计是太久没创建链表了，创建链表的时候一直将head->next指向自己（手动捂脸），然后，一脸懵逼。╮(╯▽╰)╭。希望下次别脑残的忘记申请新节点空间。