Сортировка связанного списка с альтернативными элементами, отсортированными и отсортированными в обратном порядке

Меня спросили об этом в интервью.

Список выглядит так.

a1->bn->a2->bn-1 ... ->a n->b1->NULL

Такой, что a1 ‹ a2 ‹ ... ‹ an

а также

b1 ‹ b2 ‹ ... ‹ bn

Интервьюер наложил на меня следующие ограничения:

  1. Вы должны отсортировать список на месте, то есть вам не разрешено удалять альтернативные элементы группы элементов в отдельный список.
  2. Вы должны как-то использовать шаблон, который есть в списке, чем наивный алгоритм сортировки.

Я не мог придумать решение во время интервью, да и сейчас тоже. :-(

Редактировать: Напишите код на C для сортировки этого односвязного списка.

Edit2: Мне также сказали, что я могу позаимствовать некоторые идеи из пузырьковой сортировки и воспользоваться шаблоном. Но это не должна быть «наивная» короткометражка.

Я ненавижу, когда интервьюер ставит искусственные ограничения, но работа есть работа :-)


sorting algorithm data-structures linked-list
person Saurabh    schedule 09.05.2012    source источник
comment
Итак, каков желаемый результат? Чтобы список в целом был отсортирован без различия между элементами a и b?   -  person Marcin    schedule 09.05.2012
comment
Отредактировал вопрос, чтобы ответить на комментарии   -  person Saurabh    schedule 09.05.2012
comment
@Saurabh Вы не ответили на мой вопрос. Каков желаемый результат?   -  person Marcin    schedule 09.05.2012
comment
У меня есть. Однако на вопрос уже был дан ответ: вам нужно отсортировать список на месте,   -  person Saurabh    schedule 09.05.2012
comment
@Saurabh На самом деле нет. Все, что вы сказали, это то, что список должен быть отсортирован. Вы не указали, означает ли это, что не должно быть различий между узлами a и b.   -  person Marcin    schedule 09.05.2012
comment
Кроме того, что такое наивный вид? Обычно это означает, что производительность в среднем хуже, чем у nlogn.   -  person Marcin    schedule 09.05.2012
comment
Если вам не разрешено перетасовывать список, изменяя указатели, то зачем вообще иметь связанный список? Ограничение порочное, и его соблюдение не дало бы вам работы, если бы я был интервьюером.   -  person wildplasser    schedule 09.05.2012

Ответы (2)


arrow_upward
2
arrow_downward

"Вы должны отсортировать список на месте" это требование меня смущает. Я бы подумал, что естественное решение:

  • перемещая указатели «следующие» в списке, создайте два списка. Один содержит a, а другой содержит b, перевернутые.
  • сделать слияние в этих двух списках.

Но я не уверен, нарушает ли первый шаг правило. Он находится "на месте", как я понимаю этот термин, поскольку он не копирует узлы или их данные и фактически не перемещает никаких данных. Но он удаляет альтернативные элементы в отдельный список.

Я не могу сразу сообразить, как объединить два шага в один проход.

[Редактировать: возможно, «на месте» здесь означает, что мы должны переместить данные, а не повторно связывать список. В этом случае я думаю, что проблема сложнее: эффективная сортировка слиянием на месте достаточно болезненна в массиве, если не пытаться сделать это (а) в связанном списке, (б) с альтернативными элементами в неправильном порядке]

person Steve Jessop    schedule 09.05.2012
comment
Стив, это тоже была моя первая реакция на проблему, но, по словам интервьюера, это было требованием. - person Saurabh; 09.05.2012
comment
@Saurabh: ну, если вам не разрешено повторно связывать узлы, тогда связанный список похож на массив без произвольного доступа. Так что решение будет таким же, как и для массива, но, вероятно, медленнее. - person Steve Jessop; 09.05.2012
comment
Я думаю, это то, что он имел в виду. Я приму ваш ответ. Блин, мне теперь стыдно :D - person Saurabh; 09.05.2012
comment
Я думаю, что дальнейшее улучшение заключалось в том, чтобы сначала отсортировать альтернативные элементы на месте, которые отсортированы в обратном порядке. А затем объединить два списка, которые отсортированы. - person Saurabh; 09.05.2012
comment
@Saurabh: упоминание пузырьковой сортировки напоминает мне, что пузырьковая сортировка является оптимальной сортировкой для шаблона доступа, в котором вы можете видеть память через небольшое окно, которое движется вперед, но не назад, а затем снова начинается с начала (вращающееся хранилище барабанов). Односвязный список именно такой: продвигаться вперед дешево, но чтобы вернуться назад, нужно начинать с самого начала. Я еще не придумал, как оптимизировать пузырьковую сортировку для этой мысли о входных данных. - person Steve Jessop; 09.05.2012

arrow_upward
0
arrow_downward

Чтобы сохранить его «на месте», вы можете сначала преобразовать список на месте в

a1 -> ... -> an -> b1 -> ... -> bn суб>

проходя по списку и перемещая элементы b в конец списка один за другим.

После этого вы можете перемещать элементы a вперед один за другим в режиме «пузырьковой сортировки», т. е. сканируя вперед, пока не найдете их место после границы, которая первоначально находилась перед b1.

Однако я согласен, что вопрос несколько искусственный.

person Antti Huima    schedule 09.05.2012