Испытание, если один связанный список является круговым, пройдя его только один раз

Question

Я свежее, и мне задали этот вопрос в недавнем интервью, которое я дал.

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

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

Интервьюер сказал, что ему нужен более оптимизированный способ решить эту проблему.

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

PS: По кругу в любой точке я имею в виду это. http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg

Answer 1

Интервьюер ищет, знаете ли вы трюк, который официально известен как Floyd's cycle-finding algorithm, или Tortoise and hare неофициально.

Идея состоит в том, чтобы продвигать два указателя в цикле, один перемещается дважды на итерацию, а другой только один раз. Если быстродвижущийся указатель приближается к медленному движению сзади, список имеет цикл.

Этот алгоритм определяет цикл в O(n) и O(1). «Медленный» указатель проходит через список не более одного раза, поэтому справедливо сказать, что алгоритм находит ответ в одном обходе.

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

Answer 2

Более эффективный подход состоял бы в том, чтобы иметь один итератор & проверить наличие узла, указывающего на нуль ... Этот подход должен быть в два раза эффективнее, чем приведенный выше подход.

Answer 3

Я сомневаюсь, что цель интервьюера состояла в том, чтобы узнать, знаете ли вы алгоритм поиска Floyd's cycle-found. Цель такого вопроса состояла бы в том, чтобы понять, понимаете ли вы понятия структуры данных, такие как списки, бинарные деревья и хеши.

Основная проблема с вашим ответом заключается в том, что предоставленный вами алгоритм имеет сложность O (n^2), то есть O (n) для перемещения исходного списка * O (n) для проверки того, существует ли каждый узел в второй список, на каждой итерации.

Когда интервьюер попросил вас оптимизировать свой ответ, вы могли бы предложить заменить второй связанный список другой структурой данных, которая обеспечивает более быстрый поиск, чем O (n). Например, двоичное дерево имеет сложность поиска O (logn), а хэш имеет сложность поиска O (1) (не всегда, но это общепринятое предположение), что значительно быстрее, чем использование второго связанного списка, который имеет сложность поиска O (n).

Таким образом, решение O (n) должно заменить ваш второй связанный список хешем (т. Е. HashMap, HashSet и т. Д.).

Конечно, Алгоритм определения цикла Floyd является более элегантным решением этой проблемы, поскольку он имеет лучшую сложность памяти (то есть нет необходимости хранить посещенные узлы в памяти).

Answer 4

tempNode = list; 

while((tempNode->next != list) && (tempNode->next != NULL)) 
    tempNode = tempNode->next; 

if(tempNode->next == list) 
    //list is circular 
if(tempNode->next == NULL) 
    //list is not circular 

Above two conditions can be addressed in while loop also