質問: 最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか? たとえば ``` -900->120->200->230 \ 452->700 / -10->200 ``` となっている連結リストなら ``` -900->-10->120->200->200->230->452->700 ``` としたいです。 ここでは、ノードの最初のポインタしか与えられません。 今のところは、まずそれぞれのリストの長さを取得して、それの差の絶対値|m-n|をとり、その差分だけ長い方のリストのポインタを進めて、そこから一つずつノードを比較していき、一致した数字を見つけたところを交差点とし、それまでの要素はソートし、交差点以降はそのまま連結リストに突っ込むという方法を思いついたのですが、同じ数字がランダムに現れるかもしれないので、この比較方法は現実的ではないかなとおもいました。お力を貸していただけると幸いです。 追記 共用部分の判定方法についてもアドバイスを頂けないでしょうか? 追記2 回答ありがとうございます。mergeを使用した場合O(nlogn)となってしまいますが、O(n)で実行できる方法はありますでしょうか? 追記3 merge方法自己解決しました。
回答: このマージアルゴリズムそのままでいいんじゃないでしょうか https://ja.wikipedia.org/wiki/マージ 共用部分で一致すれば、それ以降は片方のみから出力するだけで済みますね