Une question d'entretien sur javascript

Question

J'ai oublié ce que j'avais demandé à ce moment-là, car je parlais beaucoup et ma mémoire n'est pas bonne.
C'était probablement "Comment juger si une chaîne a un anneau"
Je ne me souviens que vaguement du sens...
Merci. pour m'avoir aidé à corriger le problème. Mon point principal est que je veux savoir quelle est la question.

Answer 1

C'est une question un peu difficile

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

Si vous exécutez la boucle suivante

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

Ensuite, ce sera une boucle infinie, et la température sera assignée comme suit : a => b => c => a => b ..... 这样的 abc Elle forme une boucle

---

Vous pouvez vous référer à la file d'attente circulaire et à la liste chaînée en anneau.

Alors comment juger ?

Puisqu'il a dit qu'il voulait que je juge, suivez les étapes ci-dessus.

Récursion

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

Capture d'écran

(Après avoir fini d'écrire, j'ai réalisé que j'avais fait une erreur et je l'ai réécrit... == Désolé)

Answer 2

Cette question est une question algorithmique très classique. La manière la plus classique est d'utiliser 快慢指针法 Pour des questions spécifiques, vous pouvez aller sur leetcode

.

En termes simples, définissez le pointeur rapide et le pointeur lent. Le pointeur rapide fait deux pas à la fois, et le pointeur lent fait un pas à la fois. Si les deux peuvent se rencontrer, cela signifie qu'il y a un cycle.

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