关于javascript的一道面试题
仅有的幸福
仅有的幸福 2017-07-05 10:54:36
0
2
745

忘记当时问的啥了,因为聊的比较多,记性不好.
大概是"如何判断链是否有环"
只依稀记得这个意思...
谢谢各位帮我把问题纠正下.我主要想知道问的是什么.

仅有的幸福
仅有的幸福

全部回复(2)
滿天的星座

这个问的有点厉害

var a = {
    val: 'a'
}, b = {
    val: 'b'
}, c = {
    val: 'c'
}; 

a.next = b;
b.next = c; 
c.next = a;

a.nextb
b.nextc
c.nexta
..... .....

如果执行以下循环

var temp = a; 
while(tamp){
    temp = temp.next; 
}

那么将会是个死循环,temp会被如下赋值: a => b => c => a => b ..... 这样的 abc 就是构成了一个环


你可以参考一下循环队列,环链表。

那么到底要如何判断呢?

既然他说要我判断,按照上面的做法。

递归

function isCircle(list, head){
    // 默认值 
    head = head || list; 
    if (list.next === head){ // 相等 
        console.log('是循环的'); 
        return true; 
    } else if (!list.next) { // 下一个? 不存在的 
        console.log('不是循环的');
        return false; 
    } else {
        // 继续递归 
        return isCircle(list.next, head); 
    }
}

ScreenShot

(写完发现写错又重写... = = 抱歉了)

ringa_lee

这道题目是一个非常经典的算法题,最经典的做法是使用 快慢指针法 ,具体题目可以移步 leetcode

简单来说,定义快指针和慢指针,快的一次走两步,慢的一次走一步,如果他们两个能相遇,则说明有环。

var hasCycle = function(head) {
    if(!head) return false;
    var faster = head;
    var slower = head;
    while (faster && faster.next) {
        faster = faster.next.next;
        slower = slower.next;
        if (slower === faster) return true;
    }
    return false;
};
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!