判斷鏈表是否帶環(huán)，若帶環(huán)，找到環(huán)的入口點-創(chuàng)新互聯(lián)

目前創(chuàng)新互聯(lián)已為數(shù)千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)站空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計、灞橋網(wǎng)站維護(hù)等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

#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;
	}
};
//判斷鏈表是否帶環(huán)
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;
	//于是我們從鏈表頭、與相遇點分別設(shè)一個指針，
	//每次各走一步，兩個指針必定相遇，且相遇第一點為環(huán)入口點。
	//一個從頭走，另一個從相遇點開始在環(huán)里走，
	//快指針比慢指針少走x,當(dāng)它們相遇的第一個節(jié)點就是入口點
	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);//構(gòu)建環(huán)
	if (CheckIsCircle(l1._head))
	{
		cout << (SearchCircleAccess(l1._head))->_data << endl;
	}
}

運行結(jié)果：找到的入口點的數(shù)據(jù)為6

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

網(wǎng)站題目：判斷鏈表是否帶環(huán)，若帶環(huán)，找到環(huán)的入口點-創(chuàng)新互聯(lián)
轉(zhuǎn)載來源：http://muchs.cn/article30/ddohso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站改版、商城網(wǎng)站、云服務(wù)器、軟件開發(fā)、手機(jī)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)