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 就做 (size_t)node1 < (size_t)node2 ，或者类似的东西。