面试算法 环形链表的判定_环形链表判断算法

1.题目：环形链表的判定

2.题目分析：给你一个链表，让你判定这个链表是否为环形链表，

假如是返回true ,

假如不是返回 false 

3.算法：

1.暴力的map 算法

 2.双指针算法

4.思路讲解

 ///方法一，暴力算法，假设他的name 的名字是不重复的，因为数据不重复，节点不相同
 // 使用 map 这个知识 在面试算法，两数之和，无序数组，找到返回值 
 

//2.双指针算法 
/*
首先传入一个指针，然后我们就开始判断 判定传入的指针是否为NULL 他的下一个也是否为 NULL  为下一步做准备 
建立一个快指针，一个慢指针，快指针指向下一个的下一个，慢指针指向下一个
我们建立一个 while() 循环 他的判断条件为 慢指针不等于 快指针，因为我们的执行语句的性质就是这样，主要是假如她是循环列表就一定会遇到
假如    快指针==NULL   退出循环，就返回不是循环链表。
如果     快指针  == 慢指针  他就是循环链表 
*/

代码：

/*************************************************
作者：She001
时间:2022/8/28
题目：环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪next 指针再次到达该节点,则链表中存在环
如果链表中存在环,则返回 true。否则，返回false 。
算法：
1.暴力算法
2.双指针算法
 
 
***************************************************/
#include<bits/stdc++.h>
using namespace std;
 
 
struct student 
 {
 	 string name;
 	 struct student * next;
 };
 
 ///方法一，暴力算法，假设他的name 的名字是不重复的，因为数据不重复，节点不相同
 // 使用 map 这个知识 在面试算法，两数之和，无序数组，找到返回值 
 
bool fangfa_1(struct student *head)
{
	if(head==NULL||head->next==NULL)
	{
		return false;
	}
	map<string,int>pos ;//建造一个map
	map<string ,int>::iterator f; //建立一个迭代器 
	struct student * w1=new struct student;
	w1=head;
	while(w1==NULL||w1->next!=NULL)
	{
		int n1=pos.count(w1->name);
		//cout<<w1->name<<endl;
		if(n1==1)
		{
			return true;	
		} 
		pos.insert(pair<string,int>(w1->name,1));
		w1=w1->next;
	}
	return false;
	 
	
} 
 
 
 
 
 
 
//2.双指针算法 
/*
首先传入一个指针，然后我们就开始判断 判定传入的指针是否为NULL 他的下一个也是否为 NULL  为下一步做准备 
建立一个快指针，一个慢指针，快指针指向下一个的下一个，慢指针指向下一个
我们建立一个 while() 循环 他的判断条件为 慢指针不等于 快指针，因为我们的执行语句的性质就是这样，主要是假如她是循环列表就一定会遇到
假如    快指针==NULL   退出循环，就返回不是循环链表。
如果     快指针  == 慢指针  他就是循环链表 
*/
bool fangfa_2(struct student *head)
{
	if(head==NULL ||head->next==NULL)
	{
		return false;//他不是循环指针 
	}
	struct student * w1 =new struct student;
	struct student * w2 =new struct student;
	w1=head;
	w2=head->next;
	while(w2!=w1)
	{
		if(w2==NULL||w2->next==NULL)//检测当前的位置，下一个位置是否为NULL   ,要注意的错误有NULL->next  内存错误， 所以这个判断也是为了检测下一个做是否为NULL  防止错误 
		{
			return false;
		}
		w1=w1->next;
		w2=w2->next->next; 
	}
	return true;
	
}
 
 
int main()
{
	//构建循环链表
	struct student *a1= new struct student;
	struct student *a2= new struct student;
	struct student *a3= new struct student;
	struct student *a4= new struct student;
	struct student *a5= new struct student;
	struct student *a6= new struct student;
	struct student *a7= new struct student;
	struct student *a8= new struct student;
	a1->name="1";
	a2->name="2";
	a3->name="3";
	a4->name="4";
	a5->name="5";
	a6->name="6";
	a7->name="7";
	a8->name="8";	
	a1->next=a2;
	a2->next=a3;
	a3->next=a4;
	a4->next=a5;
	a5->next=a6;
	a6->next=a7;
	a7->next=a8;
	//a8->next=NULL;//现在不是循环的；
	a8->next=a2;//这是循环的 
	
	if(fangfa_1(a1)==0)//false 的算数表达是0  true 是 1 
	{
		cout<<"false"<<endl; 
	}
	else
	{
		cout<<"true"<<endl;
	}
	
	
	if(fangfa_2(a1)==0)//false 的算数表达是0  true 是 1 
	{
		cout<<"false"<<endl; 
	}
	else
	{
		cout<<"true"<<endl;
	}
	
	 
	
	  
}