An interview question about javascript

Question

I forgot what I asked at that time, because I talked a lot and my memory is not good.
It was probably "How to judge whether a chain has a loop"
I only vaguely remember the meaning...
Thank you for your help Let me correct the question. I mainly want to know what is being asked.

Answer 1

This is a bit of a tough question

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

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

a.next is b
b.next is c
c.next is a
...

If you execute the following loop

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

Then it will be an infinite loop, and temp will be assigned as follows: a => b => c => a => b ..... Such abc constitutes a cycle

---

You can refer to circular queue and ring linked list.

So how to judge?

Since he said he wants me to judge, follow the steps above.

Recursion

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

(After I finished writing, I realized I made a mistake and rewrote it... == Sorry)

Answer 2

This question is a very classic algorithm question. The most classic method is to use the fast and slow pointer method. For specific questions, you can move to leetcode

Simply put, define the fast pointer and the slow pointer. The fast pointer takes two steps at a time, and the slow pointer takes one step at a time. If the two of them can meet, it means there is a 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;
};