Здравствуйте, kittown, Вы писали:

K>Dr.Gigabit wrote:
>>
>>> > From Microsoft:
>>> > Assume I have a linked list contains all of the alphabets from ‘A’ to
>>> > ‘Z’. I want to find the letter ‘Q’ in the list, how does you perform the
>>> > search to find the ‘Q’?
>>> >
>>> > Написать функцию "переворота" листа.
>>
>> K>В вопросе не указано, отсортирован ли list.
>>
>> Не знаю, вопрос приведен в оригинальной формулировке.
>> А какие варианты ответа?

K>Там еще не сказано, двухсвязный ли он, или односвязный.
K>Вообще ничего не сказано. Не сказано, есть ли
K>быстрый способ к произвольному элементу листа через
K>какой-нибудь дополнительный кеш.

K>Если же воспринимать задачу тупо, как односвязный список
K>без внешних кешей, с только последовательным доступом,
K>то тупо по нему пройтись до нужного элемента.

K>Если нам нужно делать это очень часто, то менять или
K>дополнять структуру данных.

K>Чего тут еще можно придумать ?

K>Mikhiail


Вопрос придумывал не я, вот оригинальный ответ:
Answer: In a linked list, we only know about the header and other elements are invisible unless we go through the node one by one. Since we have go through every single node to find ‘Q’, the search time for a linked list is linear which is O (N).