Algorithmus zum Finden des ersten gemeinsamen Knotens zweier verknüpfter Listen in js

Der Inhalt dieses Artikels befasst sich mit dem Algorithmus zum Finden des ersten gemeinsamen Knotens zweier verknüpfter Listen. Er hat einen bestimmten Referenzwert.

Problembeschreibung

Geben Sie zwei verknüpfte Listen ein und suchen Sie ihren ersten gemeinsamen Knoten.

Analyse

Angesichts der Tatsache, dass die beiden verknüpften Listen nicht die gleiche Länge haben, berechnen Sie den Längenunterschied der beiden verknüpften Listen. Anschließend muss die lange verknüpfte Liste zuerst den Längenunterschied vervollständigen und dann Die beiden verknüpften Listen können zu Walk kombiniert werden.

Code-Implementierung

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(h1, h2)
{
    var h1Len = 0, h2Len = 0;
    var cur = h1;
    
    while(cur!==null){
        h1Len++;
        cur = cur.next;
    }
    
    cur = h2;
    while(cur!==null){
        h2Len++;
        cur = cur.next;
    }
    
    var distance = 0;
    var t1, t2;
    if(h1Len > h2Len){
        t1 = h1;
        t2 = h2;
        distance = h1Len - h2Len;
    }else{
        t1 = h2;
        t2 = h1;
        distance = h2Len - h1Len;
    }
    
    while(distance !== 0){
        t1 = t1.next;
        distance--;
    }
    
    while(t1 !== t2){
        t1 = t1.next;
        t2 = t2.next;
    }
    
    return t1;
}

Verwandte Empfehlungen:

Algorithmus zur Realisierung des maximalen Werts von Schiebefenstern in js

js-Algorithmus, der zwei Stapel verwendet, um die Warteschlange zu implementieren

Das obige ist der detaillierte Inhalt vonAlgorithmus zum Finden des ersten gemeinsamen Knotens zweier verknüpfter Listen in js. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!