【剣指Offerブラシ問題:JavaScript実装】2つのチェーンテーブルの共通交点
リファレンスリンク
トピックの説明2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.(注意入力データはチェーンテーブルなので、エラーテストデータのヒントは他の方法で表示され、入力データが正しいことを保証します)
問題を解く構想. Aの長さがa+c、Bの長さがb+cであると仮定し、cが末尾共通部分長であることから、a+c+b=b+c+a が分かる.チェーンテーブルAにアクセスするポインタがチェーンテーブルの末尾にアクセスすると、チェーンテーブルBのヘッダからチェーンテーブルB へのアクセスを再開する.も同様に、チェーンテーブルBにアクセスするポインタがチェーンテーブルの末尾にアクセスすると、チェーンテーブルAのヘッダからチェーンテーブルAへのアクセスを再開させる.これにより,AとBの2つのチェーンテーブルにアクセスするポインタが交点に同時にアクセスできるように制御できる.
コード実装
トピックの説明2つのチェーンテーブルを入力し、最初の共通ノードを見つけます.(注意入力データはチェーンテーブルなので、エラーテストデータのヒントは他の方法で表示され、入力データが正しいことを保証します)
問題を解く構想.
コード実装
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
let p1=pHead1;
let p2=pHead2;
while(p1!=p2){
p1 = (!p1)? pHead1:p1.next;
p2 = (!p2)? pHead2:p2.next;
}
return p1;
}