Как определить, является ли данный одиночный связанный список циклом?

Question

Меня попросили в интервью выяснить, есть ли у одного связанного списка петля. Я искал это SO и нашел несколько ответов Вопрос с интервью: как определить цикл в связанном списке?, и я знал об этих ответах раньше, но почему-то я ответил на это по-разному, что я имел в виду из моей беседы с друзьями долгое время назад, но я не был уверен, правильно ли ответ. Если попробовать, то он работает так, как ожидалось. Почему-то интервьюер не доволен. Может кто-то уточнить, что в этом плохого?

struct node { 
int flag; 
struct node *next; 
} 

Моя идея здесь не использовать два указателя и хмель variantly но использовать единый указатель и пройти каждый узел, например:

node = node->next; 

Только это я бы сделать, это установить переменную флаг в 1, когда я когда-либо пройти узел и проверить каждый раз, например,

if (node->flag) 
{ 
    return TRUE; // implies list is a loop 
} 
else{ 
    node->flag = 1; 
} 

Другие, чем эффективность, что неправильно в таком подходе?

Answer 1

Вы используете дополнительную целую переменную flag и говорите, что если sizeof(int) на вашем компьютере составляет 4 байта и говорят, что у вас есть 100 000 узлов в связанном списке, то вы в конечном итоге будете использовать 400 000 байт. Это будет примерно 390M/.38G

Для сброса flag для всех узлов в связанном списке, хотя это O (n), вам нужно будет пересечь все 100 000 узлов. Это накладные расходы.

Теперь, если вы сравните решение на основе flag с решением с 2 переменными, то это почти одно и то же вычислительное время, но решение с 2 переменными считается очень эффективным с точки зрения памяти, поскольку оно не использует 390M памяти для идентификации цикла !

Answer 2

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

Answer 3

Для каждого элемента списка необходимы дополнительные данные (flag). Таким образом, вашему подходу нужна O (N) дополнительная память, а для подхода с двумя указателями требуется только O (1) память.

Таким образом, вы приближаетесь не к эффективности памяти.

Answer 4

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

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

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

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

Answer 5

Возможно, Hare and Turtle будет работать. Turtle interates через список обычно, по одному пункту за раз, в то время как Hare идет в два раза быстрее, по два пункта за раз. Если Hare проходит Turtle, есть петля.

Редактировать: Я вижу, это предложение уже here и что оно уже было отвергнуто ОП в его комментариях.