Разворачиваем список правильно
Oct. 13th, 2013 05:18 pmЗадачка на разворачивание односвязного списока задом наперёд и некоторые её вариации очень популярны на программистских интервью. Несмотря на её бесполезность при оценке пригодности кандидата к практической работе, из задачки можно неожиданно много выжать в качестве упражнения по кодированию на С++.
Шаг 0. Традиционное решение
Как выглядит традиционное решение? Сначала определяем стуктуруnode для представления узла списка. Полагаем, что в каждом узле хранится какой-то payload, который нас в рамках данной задачи не волнует, и указатель на следующий узел (в последнем узле он будет нулевым):
struct node
{
...
node *pnext;
};
Искомая функция получает указатель на голову списка, переворачивает список и возвращает указатель на голову перевёрнутого списка:
node *reverse(node *phead)
{
node *prhead = nullptr; // Здесь в итоге окажется указатель на голову перевёрнутого списка.
while (phead != nullptr)
{
node *p = phead->pnext;
phead->pnext = prhead;
prhead = phead;
phead = p;
}
return prhead;
}
Решение простое, работающее, и, если речь идёт о техническом интервью, обычно достаточное. Тем не менее, этот простой код можно неоднократно улучшить, а в процессе улучшения открыть для себя много нового и интересного. Этим мы и займёмся.( Read more )



