メモリの場所に応じて2つのリンクリストを並べ替える

Question

2つの二重リンクリストをマージする必要がありますが、それらの値ではありません（リストはソートされません）。 2つすべてのノードを含む単一のリストを取得したいが、メモリに表示される順序で。

この画像はもっと役立つかもしれません： http://img140.imageshack.us/i/drawing2.png/

この種のマージを実行できるアルゴリズム（できれば高速なアルゴリズム）はありますか？ たぶんこれは少し役立つでしょう：

• リストの開始ノードは常に他のリストの前にあります。
• リストには最大8192個のノードを含めることができます。
• リストはメモリの大きなブロック（メモリアロケータで使用）の空き位置を追跡するため、メモリ内のノードの場所を知っています。
• C ++で作業しています。

事前に感謝します！

Answer 1

まあ、std::listを使用していないように聞こえるので、一般的なソリューションを使用します。あなたの要件はリストをマージすることですが、ノードはメモリ内の物理的な場所の順序にする必要があります。 2つのリストを追加して、ノードのアドレスでノードを並べ替えることができます。

参照： http：//www.chiark.greenend。リンクリストのソートアルゴリズムについては、org.uk /〜sgtatham / algorithms / listsort.html を参照してください。

並べ替えるとき、 node1->value < node2->value を比較する代わりに、単に (size_t)node1 < (size_t)node2 、またはその性質に何かを行います。

Answer 2

<！> quot;マージ<！> quot;並べ替えられたリストのみをマージでき、並べ替えられていないため、ここでは少し誤解を招きます。

マージするのではなく、ソートする必要があります。

ノードへのポインターをベクターに入れます。ベクトルでstd :: sortを使用し、各ポインターをsize_t（私は思う）にキャストし、結果の数値を比較する比較ファンクターを渡します。

その後、ベクター内の結果の順序に従ってリンクリストを再配置できます。