Занятие 2 апреля: разминка

Вопрос 1.

Что делает метод hasCycle(), при условии что длина списка равна N?

01: class Node {
02: Node next;
03: Object value;
04: }
05:
06: class List {
07: Node first;
08:
09: boolean hasCycle() {
10: if (first == null) return false;
11:
12: int stepCount = 1;
13: Node t1 = first;
14: Node t2 = first;
15:
16: while (true) {
17: t1 = t2;
18: stepCount *= 2;
19: for (int i = 0; i < stepCount; i++) {
20: t2 = t2.next;
21: if (t2 == null) return false;
22: if (t2 == t1) return true;
23: }
24: }
25: }
26: }

1. Проверяет наличие цикла за время O(log(N))
2. Проверяет наличие цикла за время O(N)
3. Проверяет наличие цикла за время O(N*log(N))
4. Проверяет наличие цикла за время O(N^2)
5. Иногда тупо зависает в бесконечном цикле

Вопрос 2

Какая структура данных больше подходит для реализации обхода в ширину?

1. FIFO
2. LIFO
3. GIGO