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

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（我认为）并比较结果数字。

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