Algorithme pour trouver le premier nœud commun de deux listes chaînées en js

Le contenu de cet article concerne l'algorithme permettant de trouver le premier nœud commun de deux listes chaînées en js. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Description du problème

Entrez deux listes chaînées et trouvez leur premier nœud commun.

Analyse

Considérant que les deux listes chaînées n'ont pas la même longueur, calculez la différence de longueur des deux listes chaînées, puis la longue liste chaînée doit d'abord compléter la différence de longueur, puis les deux listes chaînées peuvent être combinées Walk.

Implémentation du code

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

Recommandations associées :

Algorithme pour réaliser la valeur maximale de la fenêtre coulissante en js

Algorithme d'utilisation de deux piles pour implémenter la file d'attente en js

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!