Cracking the Coding Interview, 6-е издание, 2.8

Задача: заданный круговой связанный список, реализуйте algoirthm, который возвращает node в начале цикла.

Ключ ответа дает более сложное решение, чем то, что я предлагаю. Что случилось с моим?:

public static Node loopDetection(Node n1) {
 ArrayList<node> nodeStorage = new ArrayList<node>();
 while (n1.next != null) {
 nodeStorage.add(n1);
 if (nodeStorage.contains(n1.next)) {
 return n1;
 }
 else {
 n1 = n1.next;
 }
 }
 return null;
}
</node></node>
2 ответа

Ваше решение O(n^2) time (каждый contains() в ArrayList - это время O(n)) и O(n) (для хранения nodeStorage), тогда как "более сложное" решение - O(n) time и O(1).

В книге предлагается следующее решение, кому интересно: O(n) время и O(1) пробел:

Если мы переместим два указателя, один со скоростью 1 и другой со скоростью 2, они закончат встречу, если связанный список имеет цикл. Зачем? Думать около двух автомобилей, движущихся по трассе - чем быстрее автомобиль будет всегда проходить медленнее! Трудная часть здесь - поиск начала цикла. Представьте себе, как аналог, два человека, мчащиеся по дорожке, в два раза быстрее других. Если они начинаются в одном и том же месте, когда они последуют в следующий раз? Они последуют в начале следующего круга. Теперь давайте предположим, что у Fast Runner был начальный уровень k метров на n ступенчатый круг. Когда они последуют в следующий раз? Они будут встречаться к метрам до начало следующего круга. (Почему? Fast Runner сделал бы k + 2 (n - k) шаги, включая его начало, и Slow Runner сделали бы n - k шаги. Оба будут к шагам до начала цикла.) Теперь, идя назад к проблеме, когда Fast Runner (n2) и Slow Runner (n1) являются перемещаясь вокруг нашего кругового связанного списка, n2 начнет цикл, когда n1 входит. В частности, он будет иметь начало k, где k - число узлов перед циклом. Поскольку n2 имеет голову начало k узлов, n1 и n2 будут соответствовать k узлам до начала петля. Итак, теперь мы знаем следующее: 1. Головка - это k узлов из LoopStart (по определению). 2. MeetingPoint для n1 и n2 - это k узлов из LoopStart (как показано выше). Таким образом, если мы переместим n1 обратно в Head и сохраним n2 в MeetingPoint, и перемещайте их в одинаковом темпе, они будут встречаться на LoopStart.

LinkedListNode FindBeginning(LinkedListNode head) {
 LinkedListNode n1 = head;
 LinkedListNode n2 = head;
 // Find meeting point
 while (n2.next != null) {
 n1 = n1.next;
 n2 = n2.next.next;
 if (n1 == n2) {
 break;
 }
 }
// Error check - there is no meeting point, and therefore no loop
 if (n2.next == null) {
 return null;
 }
 /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps
 /* from the Loop Start. If they move at the same pace, they must
 * meet at Loop Start. */
 n1 = head;
 while (n1 != n2) {
 n1 = n1.next;
 n2 = n2.next;
 }
 // Now n2 points to the start of the loop.
 return n2;
 }


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

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

(решение amir имеет очень похожую проблему в языках, где == сравнивает объекты, а не ссылки. Например, в Swift вам придется использовать === (сравнивает ссылки), а не == (сравнивает объекты )).

licensed under cc by-sa 3.0 with attribution.