Сортировка двух связанных списков по памяти

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 (я думаю) и сравнивает полученные числа.

Затем вы можете переставить связанные списки в соответствии с результирующим порядком в векторе.