带环问题
- 判断链表是否带环
- 如果带环则环长是多少
- 求环的入口点
1、判断单链表是否带环
思路:设置一个快指针,每次走两步,再设置一个慢指针每次走一步。然后判断是否有交点即可。
就好比你在环形跑道和别人赛跑,不管你俩速度如何,只要他比你快,总会追上你将你套圈(甩你好几圈的意思)
基于这种思路实现如下代码:
//判断链表是否带环
bool IsExistLoop(Node* Head)
{
if (NULL == Head)
return true;
Node *Fast = Head;
Node *Slow = Head;
//如果链表不带环,则Fast肯定先走到NULL
while (Fast&& Fast->_next){
Fast = Fast->_next->_next;
Slow = Slow->_next;
if (Fast == Slow)
return true;
}
if (Fast == NULL || Fast