js 内の 2 つのリンクされたリストの最初の共通ノードを見つけるアルゴリズム

不言
リリース: 2018-07-23 11:00:14
オリジナル
1507 人が閲覧しました

この記事では、js で 2 つのリンクされたリストの最初の共通ノードを見つけるためのアルゴリズムを共有します。必要な友人はそれを参照できます。

問題の説明

2 つのリンク リストを入力し、それらの最初の共通ノードを見つけます。

分析

2 つのリンク リストが同じ長さではないことを考慮して、2 つのリンク リストの長さの差を計算します。次に、長いリンク リストが長さの差を完全にする必要があり、その後、2 つのリンク リストを一緒に歩くことができます。

コード実装

/*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;
}
ログイン後にコピー

関連する推奨事項:

js でスラ​​イディング ウィンドウの最大値を実装するアルゴリズム

js で 2 つのスタックを使用してキューを実装するアルゴリズム

以上がjs 内の 2 つのリンクされたリストの最初の共通ノードを見つけるアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ソース:php.cn
このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
最新の問題
人気のチュートリアル
詳細>
最新のダウンロード
詳細>
ウェブエフェクト
公式サイト
サイト素材
フロントエンドテンプレート