本文主要是介绍面试题----单链表带环问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
关于单链表带环问题：1、怎样判断一个单链表是否带环；2、如果带环，环的长度怎么计算；
3、如果带环，怎么求环的入口；
1、怎样判断一个单链表是否带环：我们知道，单链表如果带环，那么从链表头开始遍历就会进入死循环。其实我们可以用上篇博客中提到的两个指针移动的思想来求解，在这里可以让两个指针移动速度不同，首先令两个指针fast和slow同时指向链表头部，然后每次使fast走两步（fast和slow不规定必须走几步，只要fast比slow走的快就可以），使slow走一步，只要链表中有环，那么fast和slow总会相遇。
2、如果带环，环的长度怎么计算：首先利用1我们可以得到fast和slow的第一次相遇，把它标记起来，给一个变量length，让它初始为0，然后继续让fast和slow向后走，每走一次length加一，等到它们再次相遇的时候，得到的length就是环的长度。
3、如果带环，怎么求环的入口：同样利用1得到fast和slow第一次相遇，然后分别在链表头和相遇点各设一个指针，两个指针每次都向后走一步，再次相遇的点（相遇的第一个点）就是环的入口点。
下面我用一张图来模拟一下判断是否带环时指针移动的过程，后面两个问题大家可以自己画图验证一下，看能不能得到想要的结果。
下面附上代码：
bool IsLoop(Node* pHead) //判断一个链表是否带环
{if(pHead == NULL)return false;Node* fast = pHead;Node* slow = pHead;while(fast != NULL && fast->_next != NULL) //如果不带环，则fast先走到NULL{fast = fast->_next->_next;slow = slow->_next;if(fast == slow)break;}if(fast != NULL && fast->_next != NULL)return true;elsereturn false;
}size_t LoopLength(Node* pHead) //求链表中环的长度
{if(pHead == NULL)return 0;if( !(IsLoop(pHead)) )return 0;Node* fast = pHead;Node* slow = pHead;size_t length = 0;bool firstmeeting = false;while(1){fast = fast->_next->_next;slow = slow->_next;if(fast == slow && firstmeeting == true) //第二次相遇break;if(fast == slow && firstmeeting == false ) //第一次相遇{firstmeeting = true;}if(firstmeeting)length++;}return length;}Node* FindLoopEntrance(Node* pHead) //求环的入口点
{if(pHead == NULL)return NULL;if( !(IsLoop(pHead)) )return NULL;Node* fast = pHead;Node* slow = pHead;while(1){fast = fast->_next->_next;slow = slow->_next;if(fast == slow){slow = pHead;break;}}while(1){fast = fast->_next;slow = slow->_next;if(fast == slow)break;}return slow;
}
这篇关于面试题----单链表带环问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
