關于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;};