Вопрос: Изменение связанного списка


Вам предоставляется единый связанный список a->b->c->d->1->2->3->4->e->f->g->h->5->6->7->8 , Вы должны изменить этот список, чтобы он выглядел a->1->b->2->c->3->d->4->e->5->f->6->g->7->h->8 ,

Мой подход использует дополнительный список, в котором мы удаляем числа из списка и храним их отдельно. Затем объединить списки вместе. Может ли кто-нибудь предложить лучшие методы для этого?


3


источник


Ответы:


У меня было бы два итератора. Попросите один (итератор A) пройти через список, остановившись, когда вы нажмете число, а другой (итератор B) останется в начале списка. Когда вы нажмете число, вставьте узел в итератор A после узла на итераторе B, затем переместите итератор B вверх. Таким образом, вам не нужно составлять отдельный список.

EDIT: удалите элемент на итераторе A после того, как вы вставьте его в B (благодаря Tudor для ловли).


8



Возьмите 2 указателя и увеличьте 2 указателя, пока не получите число, и как только вы получите номер, удалите узел и вставьте его после первого указателя.

Поскольку у него вопрос о собеседовании, интервьюер может посмотреть, как вы обрабатываете все угловые случаи, например, список равен нулю, только два узла (1-char & 1-int), количество символов и целочисленный узел различаются по числу в блок и т.д.


1