この記事では、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 サイトの他の関連記事を参照してください。