

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか？

たとえば

[code]

    -900->120->200->230
                       \
                        452->700
                       /
               -10->200
    
[/code]

となっている連結リストなら

[code]

    -900->-10->120->200->200->230->452->700
    
[/code]

としたいです。  
ここでは、ノードの最初のポインタしか与えられません。

今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。

追記  
共用部分の判定方法についてもアドバイスを頂けないでしょうか？

追記2  
回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか？  
追記3  
merge方法自己解決しました。


CC BY-SA 4.0
2020-04-03T16:21:18.420
65336
2020-04-04T07:12:40.413
2020-04-04T07:12:40.413
38330
38330
question
アルゴリズム データ構造
2つのいくつかのノードを共有する連結リストをソートしたい


このマージアルゴリズムそのままでいいんじゃないでしょうか  
[https://ja.wikipedia.org/wiki/マージ](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8)

共用部分で一致すれば、それ以降は片方のみから出力するだけで済みますね


CC BY-SA 4.0
2020-04-03T20:01:49.123
65340
2020-04-03T20:01:49.123
9811
65336
answer


マージは通常のマージを行えば良いでしょう。

末尾で共有されているノードの先頭に到達したかどうかの判定は、連結リストをどのように実装しているかによって変わります。

ポインタなどで管理されておりノード間の physical equality
が判定できるのであれば、これを使えば良いです。共有されている部分を単に繋げるのかノード数を倍にするのかで処理が変わってくるので注意してください。

physical equality が使えない場合、

[code]

    ... --- 10 --- 20 --- 30
                       |
    ... --- 15 --- 20 -|
    
[/code]

と

[code]

    ... --- 10 --- 20 --- 30
                |
    ... --- 15 -|
    
[/code]

の区別がつかないので特別なことはせず単に新しいノードを作っていくということになりそうです。ただし、共有している部分から先を 2 つに増やすのではなく 1
つのままにするということであれば共有部分であることを示すフラグをデータ構造の方に入れないと厳しそうです。


CC BY-SA 4.0
2020-04-04T05:11:31.590
65347
2020-04-04T05:11:31.590
19110
65336
answer