mstone: (Default)
Задачка на разворачивание односвязного списока задом наперёд и некоторые её вариации очень популярны на программистских интервью. Несмотря на её бесполезность при оценке пригодности кандидата к практической работе, из задачки можно неожиданно много выжать в качестве упражнения по кодированию на С++.

Шаг 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 )
mstone: (Default)
Создатели языка C# — это рыцари без страха, упрёка, сомнений и рефлексии. Майкрософтовский документ про новые фичи в C# 4.0 первым делом порадовал следующим:
   C# 4.0 introduces a new static type called dynamic.

Profile

mstone: (Default)
mstone

October 2013

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 25th, 2017 11:43 am
Powered by Dreamwidth Studios