腾讯面试：龟兔赛跑判断链表是否带环

 关注

“脚本之家

”，与百万开发者在一起

出处：爱码有道（ID：aimayoudao）

如若转载请联系原公众号

大家好，我是道哥。今天，我们来看一道非常有趣的腾讯面试题，题目如下：

有一个单链表，已知其头指针，判断它是否带环？要求时空复杂度尽可能低。

显然，我们首先自然要清楚，什么是不带环的单链表？什么是带环的单链表？

不带环的单链表很常见，比如：

带环的单链表不太常见，比如：

如果你还处于懵圈的状态，那也不要着急哦。比赛的赛道总应该见过吧，且看直赛道和环赛道：

直赛道

环赛道

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

一. 暴力解法

不带环，意味着一直往前走，必定会有尽头，对吧！ 带环，意味着一直往前走，总在循环中转圈，没有尽头。

然而，这里的问题是：“一直”是什么意思？到底走多久才算一直？这是我们遇到的难点，必须面对这个问题。

总不能用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
}

很显然，这种不严密的暴力解法，无法通过腾讯的面试。

二. 标记解法

接下来，我们思考下：环的本质是什么？说白了，环就是：总会走过曾经走过的地方。是啊，好马还吃回头草呢？

正所谓走过路过不要错过，只要是走过的地方，都做一个标记，下次如果再遇到，说明这条路就是一条环状的路。

具体很简单：把走过结点的地址，塞入到hashmap中，每走过一个结点，就判断结点地址是否已在hashmap中。

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

三. 龟兔赛跑

利用龟兔赛跑的启发，我们可以有比较圆满的解答，让时间复杂度和空间复杂度尽可能低，并且能通过腾讯面试。

为了更形象直观地呈现，我画了两张动图。对于直赛道而言，在龟兔赛跑中，乌龟是永远没法追赶上兔子的。别忘了，兔子不会睡觉哦，如下：

对于环形赛道而言，兔子的速度远大于乌龟，所以，总有一天，兔子会再次追上乌龟。你看看兔子追上乌龟的那个得意的表情啊，高兴坏了，Yeah:

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

#include<iostream>
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;
}

经测试，完全正确。龟兔赛跑，真的很有趣啊，也顺便通过了腾讯的面试。

这道腾讯面试题，不难，也不容易，关键还是在于思路。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

  推荐阅读：

每日打卡赢积分兑换书籍入口