判断链表是否带环，若带环，找到环的入口点-创新互联

目前创新互联已为数千家的企业提供了网站建设、域名、网站空间、网站改版维护、企业网站设计、灞桥网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
	T _data;
	LinkNode* _next;
	LinkNode(const T& x)
		:_data(x)
		, _next(NULL)
	{}
};
template<class T>
class ListNode
{
	//为了安全性
private:
	ListNode(const ListNode& l)
	{}
	ListNode<T>& operator=(ListNode l)
	{}
public:
	//程序限制
	LinkNode<T>* _head;
public:
	ListNode()
		:_head(NULL)
	{}
	~ListNode()
	{
		while (_head)
		{
			PopBack();
		}
	}
	void PushBack(const T& x)
	{
		LinkNode<T>* tmp = new  LinkNode<T>(x);
		if (_head == NULL)
			_head = tmp;
		else
		{
			LinkNode<T>* cur = _head;
			while (cur->_next)
				cur = cur->_next;
			cur->_next = tmp;
		}
	}
	void PopBack()
	{
		if (_head == NULL)
			return;
		if (_head->_next == NULL)
		{
			delete _head;
			_head = NULL;
		}
		else
		{
			LinkNode<T>* cur = _head;
			while (cur->_next&&cur->_next->_next)
			{
				cur = cur->_next;
			}
			LinkNode<T>* del = cur->_next;
			cur->_next = NULL;
			delete del;
		}
	}
	LinkNode<T>* Search(const T& x)
	{
		if (_head == NULL)
			return  NULL;
		LinkNode<T>*  cur = _head;
		while (cur->_data != x)
			cur = cur->_next;
		return cur;
	}
};
//判断链表是否带环
template<typename T>
bool CheckIsCircle(LinkNode<T>* head)
{
	if (head == NULL || head->_next == NULL)
		return false;
	LinkNode<T>* fast, *slow;
	fast = slow = head;
	while (fast&&fast->_next)
	{
		fast = fast->_next->_next;
		slow = slow->_next;
		if (fast == slow)
			return true;
	}
	return false;
}
template<class T>
LinkNode<T>* SearchCircleAccess(LinkNode<T>* head)
{
	if (head == NULL||head->_next==NULL)
		return NULL;
	LinkNode<T>* fast = head;
	LinkNode<T>* slow = head;
	while (fast&&fast->_next)
	{
		fast = fast->_next->_next;
		slow = slow->_next;
		if (fast == slow)
			break;
	}
	slow = head;
	//于是我们从链表头、与相遇点分别设一个指针，
	//每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。
	//一个从头走，另一个从相遇点开始在环里走，
	//快指针比慢指针少走x,当它们相遇的第一个节点就是入口点
	while (slow != fast)
	{
		slow=slow->_next;
		fast = fast->_next;
	}
	return slow;
}
void Test1()
{
	ListNode<int> l1;
	l1.PushBack(1);
	l1.PushBack(2);
	l1.PushBack(3);
	l1.PushBack(4);
	l1.PushBack(5);
	l1.PushBack(6);
	l1.PushBack(7);
	l1.PushBack(8);
	l1.PushBack(9);
	(l1.Search(9))->_next = l1.Search(6);//构建环
	if (CheckIsCircle(l1._head))
	{
		cout << (SearchCircleAccess(l1._head))->_data << endl;
	}
}

运行结果：找到的入口点的数据为6

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

网站题目：判断链表是否带环，若带环，找到环的入口点-创新互联
转载来源：https://www.cdcxhl.com/article30/ddohso.html

成都网站建设公司_创新互联，为您提供ChatGPT、网站改版、商城网站、云服务器、软件开发、手机网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联