腾讯面试：龟兔赛跑判断链表是否带环
大家好，我是道哥。今天，我们来看一道非常有趣的腾讯面试题，题目如下：
有一个单链表，已知其头指针，判断它是否带环？要求时空复杂度尽可能低。
带环的单链表不太常见，比如：
如果你还处于懵圈的状态，那也不要着急哦。比赛的赛道总应该见过吧，且看直赛道和环赛道：
直赛道
接下来，我们来判断赛道是否带环，请注意要求：时间复杂度和空间复杂度尽可能低。
一. 暴力解法
不带环，意味着一直往前走，必定会有尽头，对吧！ 带环，意味着一直往前走，总在循环中转圈，没有尽头。
然而，这里的问题是：“一直”是什么意思？到底走多久才算一直？这是我们遇到的难点，必须面对这个问题。
总不能用while死循环来做吧，如果真有环，程序就陷入了死循环，无法走出来，那这个程序就没啥意义了。
所以，必须考虑限制次数，比如往后走100万次，倘若还没有终点，那么可以认为这个链表就是带环的链表。
稍微有点逻辑的人都知道，这个解法是不严密的，假如这个链表真的有200万个结点呢？那就明显产生误判。
我在LeetCode上验证了思路，发现居然通过了所有的测试用例，根本原因还是测试用例太少，Go代码如下：
func hasCycle(head *ListNode) bool {count := 0max := 1000000for ; head != nil && count < max; {count++head = head.Next}if count == max {return true}return false}
很显然，这种不严密的暴力解法，无法通过腾讯的面试。
二. 标记解法
接下来，我们思考下：环的本质是什么？说白了，环就是：总会走过曾经走过的地方。是啊，好马还吃回头草呢？
正所谓走过路过不要错过，只要是走过的地方，都做一个标记，下次如果再遇到，说明这条路就是一条环状的路。
具体很简单：把走过结点的地址，塞入到hashmap中，每走过一个结点，就判断结点地址是否已在hashmap中。
可是，这里引入了哈希表，所以，空间复杂度就是O(N)了。显然，这不是最好的方式，也自然没法通过腾讯面试。
三. 龟兔赛跑
利用龟兔赛跑的启发，我们可以有比较圆满的解答，让时间复杂度和空间复杂度尽可能低，并且能通过腾讯面试。
为了更形象直观地呈现，我画了两张动图。对于直赛道而言，在龟兔赛跑中，乌龟是永远没法追赶上兔子的。别忘了，兔子不会睡觉哦，如下：
对于环形赛道而言，兔子的速度远大于乌龟，所以，总有一天，兔子会再次追上乌龟。你看看兔子追上乌龟的那个得意的表情啊，高兴坏了，Yeah:
受此启发，我们可以在链表中考虑快慢指针，快指针每次走2步，慢指针每次走1步，这样就完美地模拟了上述的龟兔赛跑场景。这次采用C++语言，程序如下：
using namespace std;typedef struct node{int data;struct node *next;}Node;Node *createList(int n){Node *p = new Node[n];for( int i = 1; i < n; ++i){p[i - 1].next = &p[i];p[i - 1].data = i;}p[n - 1].next = NULL;p[n - 1].data = n;return p;}Node *createListWithRing(int n){Node *p = new Node[n];for( int i = 1; i < n; ++i){p[i - 1].next = &p[i];p[i - 1].data = i;}p[n - 1].next = &p[n/2];p[n - 1].data = n;return p;}//pFast相当于兔子，pSlow相当于乌龟bool listHasRing(Node *p){Node *pSlow = &p[0];Node *pFast = &p[1];while(NULL != pSlow && NULL != pFast -> next){if(pSlow == pFast){return true;}pSlow = pSlow -> next;pFast = pFast -> next ->next;}return false;}int main(){Node *head = createList(10);cout << listHasRing(head) << endl;delete [] head;head = createListWithRing(10);cout << listHasRing(head) << endl;delete [] head;return 0;}
经测试，完全正确。龟兔赛跑，真的很有趣啊，也顺便通过了腾讯的面试。
朋友，点个“赞”和“在看”鼓励下呗