根據內存位置對兩個鏈表進行排序

Question

我需要合併兩個雙鏈表，但不是按它們的值（列表不排序）。 我想獲得一個列表，其中包含兩個節點中的所有節點，但是按它們在內存中的顯示順序排列。

也許這個形象可以幫助更多： http://img140.imageshack.us/i/drawing2.png/

是否有任何的算法（最好是一快一），可以做這樣的合併？ 也許這有點幫助：

• 列表的開始節點總是在其他節點之前。
• 一個列表最多可以有8192個節點。
• 我知道節點在內存中的位置，因爲這些列表跟蹤大塊內存中的空閒位置（用於內存分配器）。
• 我用C++工作。

在此先感謝！

Answer 1

好吧，聽起來好像你沒有使用std::list，所以我會用通用的解決方案。由於您的要求是合併列表，但節點按照存儲器中物理位置的順序排列。您可能只需追加兩個列表，然後按節點地址對節點進行排序。

參見：http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html用於鏈接列表的排序算法。

當排序，而不是比較node1->value < node2->value，只是做(size_t)node1 < (size_t)node2，或東西的性質。

Answer 2

「合併」在這裏有點讓人誤解，因爲您只能合併已排序的列表，而您的未排序。

您需要排序，而不是合併。

將指向節點的指針放入向量中。在向量上使用std :: sort，並傳遞一個比較函數，將每個指針轉換爲size_t（我認爲）並比較結果數字。

然後，您可以根據向量中的結果順序重新排列鏈接列表。