您的位置 首页 java

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

今天,我们来看一道非常有趣的腾讯面试题,题目如下:

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

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

不带环的单链表很常见,比如:

带环的单链表不太常见,比如:

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

直赛道

环赛道

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

一. 暴力解法

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

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

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

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

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

文章来源:智云一二三科技

文章标题:腾讯面试:龟兔赛跑判断链表是否带环

文章地址:https://www.zhihuclub.com/193677.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图