Eine Interviewfrage zu Javascript

Question

Ich habe vergessen, was ich damals gefragt habe, weil ich viel geredet habe und mein Gedächtnis nicht gut ist.
Es war wahrscheinlich „Wie kann ich beurteilen, ob eine Kette einen Ring hat?“
Ich erinnere mich nur vage an die Bedeutung ...
Danke Ich möchte vor allem wissen, was die Frage ist.

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

如果执行以下循环

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