JS – linked list cycle

Uczymy się pisać algorytm, który sprawdza, czy lista wiązana ma cykl, to jest czy się zapętla. Do dzieła.

Na początku klasa Node:


class Node{
    constructor(val){
        this.val = val;
        this.next = null;
    }
}

Teraz tworzymy 3 nodes, zapętlone:

let a = new Node("a");
let b = new Node("b");
let c = new Node("c");

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

Teraz nasz algorytm:

function hasCycle(node){

    let slow = node;
    let fast = node;

    while(fast !== null && fast.next !== null){
        
        slow = slow.next;
        fast = fast.next.next;

        if(slow === fast)
            return true;
    }

    return false;
}

console.log(hasCycle(a));
//true

Algorytm działa w ten sposób, że mamy szybki i wolny wskaźnik. Szybki skacze o 2 do przodu, wolny o 1 do przodu. Jeżeli lista się zapętla, to prędzej czy później szybki i wolny będą wskazywać to samo miejsce:

f,s
a ---> b --- c-|
^--------------|

       s     f
a ---> b --- c-|
^--------------|

       f      s
a ---> b --- c-|
^--------------|

f,s             
a ---> b --- c-|
^--------------|

Ok, teraz zobaczmy jak działa bez zapętlenia:

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

console.log(hasCycle(a));
//false

Mechanizm jest taki:

f,s
a -------> b ---------> c -----------> null

           s            f (f.next null, koniec pętli, false, cyklu nie ma)
a -------> b ---------> c -----------> null