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

Question

Мне нужно объединить два двусвязных списка, но не по их значениям (списки не сортируются).Я хочу получить единый список, содержащий все узлы из двух, но в том порядке, в котором они появляются в памяти.

Возможно, это изображение поможет больше:http://img140.imageshack.us/i/drawing2.png/

Есть ли какой-нибудь алгоритм (желательно быстрый), который может выполнить такое слияние?Возможно, это немного полезно:

• начальный узел списков всегда находится раньше остальных.
• список может содержать до 8192 узлов.
• Я знаю, где в памяти расположены узлы, поскольку списки отслеживают свободное место в большом блоке памяти (используемом в распределителе памяти).
• Я работаю на С++.

Заранее спасибо!

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

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