關於javascript的一道面試題

Question

忘記當時問的啥了,因為聊的比較多,記性不好.
大概是"如何判斷鍊是否有環"
只依稀記得這個意思...
謝謝各位幫我把問題糾正下.我主要想知道問的是什麼.

Answer 1

這個問的有點厲害

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

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

a.next 是 b
b.next 是 c
c.next 是 a

c.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

🎜🎜🎜 🎜（寫完發現寫錯又重寫... = = 抱歉了）🎜

Answer 2

這題目是一個非常經典的演算法題，最經典的做法是使用 快慢指針法 ，具體題目可以移步 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;
};