关于javascript的一道面试题

问题描述

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

问题解答

这个问的有点厉害

var a = { val: ’a’}, b = { val: ’b’}, c = { val: ’c’}; a.next = b;b.next = c; c.next = a;

a.next 是 bb.next 是 cc.next 是 a..... .....

如果执行以下循环

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

（写完发现写错又重写... = = 抱歉了）

这道题目是一个非常经典的算法题，最经典的做法是使用 快慢指针法 ，具体题目可以移步 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;};