c++ - 根据内存位置对两个链表进行排序

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只比较 do(size_t)node1 < (size_t)node2或类似的东西。

Answer 2

“合并”在这里有点误导，因为您只能合并已排序的列表，而您的未排序。

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

将指向节点的指针放入向量中。在向量上使用 std::sort ，并传递一个比较函子，该函子将每个指针转换为 size_t （我认为）并比较结果数字。

然后，您可以根据向量中的结果顺序重新排列链接列表。