腾讯访谈：龟兔赛跑，判断链表是否有环面试腾讯会议要开视频吗

大家好，我是道哥，今天给大家看一道很有意思的腾讯面试题，题目如下：

有一个单链表，给定它的头指针，判断它是否有环？时间和空间复杂度要尽可能低。

显然，我们首先要明白什么是无循环的单链表？什么是有循环的单链表？

无环的单链表很常见，例如：

带有循环的单链表不太常见，例如：

如果你还是一头雾水，别担心，你肯定见过赛道，我们来看看直线赛道和环形赛道：

直轨

电路

接下来我们来判断赛道是否有回环，注意要求：时间复杂度和空间复杂度要尽量低。

1. 暴力破解

没有戒指，就意味着你一直往前走，一定会有尽头，对吧？有戒指，就意味着你一直往前走，一直绕圈子，没有尽头。

但这里的问题是：什么叫“始终”？要多久才算“始终”？这是我们遇到的困难，也是我们必须面对的问题。

不能用while无限循环来做这件事。如果有循环，程序就会陷入无限循环，无法跳出。那么程序就毫无意义了。

所以我们要考虑限制次数，比如我们回溯100万次还是没有尽头，那么我们可以认为这个链表是一个带环的链表。

稍微有点逻辑的人都知道，这个解法不严谨。如果这个链表真的有200万个节点怎么办？那显然是误判。

我在 LeetCode 上验证了这个想法，发现它通过了所有测试用例。根本原因是测试用例太少了。Go 代码如下：

func hasCycle(head *ListNode) bool {
    count := 0    max := 1000000    for ; head != nil && count < max; {        count++        head = head.Next    }
    if count == max {        return true    }
    return false}

显然，这种不严谨的暴力破解方法不会通过腾讯的面试。

2. 标记解决方案

接下来我们来思考一下：循环的本质是什么？简单来说，循环就是：你总会回到你之前去过的地方。是啊，一匹好马总会回到它之前去过的牧场，对吧？

俗话说，路过的地方不要错过，去过的每一个地方都做个记号，如果下次再遇见，就说明这条路是一条循环的路。

具体方法很简单：把你传递过的节点地址都放入hashmap中，每传递一个节点，就检查一下这个节点地址是否已经在hashmap中。

但是这里引入了哈希表，所以空间复杂度是O(N)，显然这不是最好的办法，自然也就过不了腾讯的面试。

3. 龟兔赛跑

受到龟兔赛跑的启发，我们可以得出一个比较满意的方案，使得时间复杂度和空间复杂度尽可能低，并且能够通过腾讯的面试。

为了更加形象直观的呈现，我画了两张动图，直线赛道，龟兔赛跑，乌龟永远追不上兔子，别忘了兔子是不会睡觉的，如下图：

对于圆形的赛道，兔子的速度比乌龟快很多，所以总有一天，兔子会再次追上乌龟。看兔子追上乌龟后那得意洋洋的表情，好开心呀。

‍

受此启发，我们可以考虑链表中的快指针和慢指针，快指针每次走2步，慢指针每次走1步，这样就完美模拟了上面提到的龟兔赛跑场景，这次用的是C++语言，程序如下：

#includeusing 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;}

测试了一下，完全正确，龟兔赛跑真的很有趣，而且我也通过了腾讯的面试。

这道腾讯面试题说难也难，说简单也简单，关键在于思路，我们也会一步步来，争取每一篇文章讲清楚一个事情，也希望大家看完之后有所收获，感到快乐。