#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
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。