[解決済み] 2つのリンクリストがマージされるかどうかをチェックします。もしそうなら、どこで？

質問

この質問は古いかもしれませんが、回答が思いつきませんでした。

異なる長さの2つのリストがあるとします。 点で結合され 合流点はどこにあるのでしょうか？

条件です。

1. 長さがわからない
2. 各リストを一度だけパースする必要があります。

どのように解決するのですか？

もし

• は、quot; modification is not allowed" は、quot; you may change but in the end in the restored" という意味であり、また
• はリストを正確に反復することができます。 2 回

の場合、以下のアルゴリズムが解決策となります。

まず、数字です。 最初のリストが長さ a+c で、2 番目のリストが長さ b+c であり、ここで c は共通の尾部(マージポイント以降)の長さである。 これらを次のように表すことにする。

x = a+c
y = b+c

長さが分からないので、計算します。 x と y を追加で反復させることなく実行できます。

次に、それぞれのリストを繰り返し、繰り返しながら逆引きをします もし両方のイテレータが同時にマージポイントに到達したら、単に比較することでそれを見つけます。 そうでなければ、一方のポインタがもう一方のポインタよりも先にマージポイントに到達することになります。

その後、もう一方のイテレータがマージポイントに到達しても、共通の末尾に進むことはありません。代わりに、前にマージポイントに到達したリストの元の先頭に戻ります! ですから、変更されたリストの最後 (すなわち、もう一方のリストの元の先頭) に到達する前に、彼は a+b+1 の繰り返しをすることになります。 これを z+1 .

最初にマージポイントに到達したポインタは、リストの最後に到達するまで反復し続けます。 このポインタが行った反復の回数は計算され、次のようになります。 x .

次に、このポインタは反復して戻り、再びリストを反転させます。 しかし今度は、元々開始したリストの先頭には戻りません! その代わり、もう一方のリストの先頭に行きます! このポインタの繰り返し回数は次のように計算されます。 y .

ということで、次のような数字がわかります。

x = a+c
y = b+c
z = a+b

ということがわかります。

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

これで問題解決。