2. Цикл в списке

Created Wednesday 08 October 2014

https://www.youtube.com/watch?v=cR0v9hQm7kE

Определение цикла в списке

Linked List

Есть некоторая информация и указатель на следующий элемент списка
Последний указатель указывает на null
Необходимо узнать, если в этом списке цикл.

Цель: получив указатель на первый элемент списка решить, есть ли в этом списке цикл

Решение 1

Обойдём список последовательно с 1-го элемента до последнего. Если найден последний элемент (указывает на null), вернём нет цикла, иначе вернём есть цикл
Проверка:
  1. Если нет цикла, то алгоритм дойдёт до последнего элемента
  2. Если цикл есть, то алгоритм никогда не остановится — плохой алгоритм

Решение 2

Обойти список, и для каждого пройденного элемента пометить, что он уже посещён
Для этого надо либо строить отдельную структуру данных, либо изменять сами элементы списка (выберем 2-й вариант)
Проблемы:
  1. Не всегда можно менять элементы списка
  2. Чтобы добавить новое поле, которое можно проверить, нужно пройти по всем элементам списка, в котором может быть цикл — это возвращает нас к первому неправильному решению

Решение 3

Вспомогательная структура данных (массив)
Обходя список последовательно, заносим в ar[i] адрес[node[i]] и проверим, есть ли уже такой адрес в массиве. Если есть — цикл найден.

Решение 4

Как и решение 3, но вместо массива адресов можно использовать уравновешенное бинарное дерево
timecomp Q(N lg N)
memorycomp Q(N)

Решение 5

Используя хэш-таблицы можно проверять любой элемент за постоянное среднее время
timecomp Q(N)
memorycomp Q(N)

Решение 6

Пусть все адреса элементов списка находятся в линейном пространстве адресов (упорядочены по возрастанию (не по порядку самих элементов))
diff — разность между последним и первым адресом
Если на каком-то шаге обхода количество пройденных элементов становится больше, чем diff, то есть цикл.
mem. c. Q(const)
time. c. Q(max. addr. - min. addr.)

Решение 7 — лучшее

  1. c. Q(n), m. c. Q(c)
Если два человека бегут в одну сторону по кругу с разными скоростями, то при достаточном времени они неизбежно встретятся; для прямой только если скорость последнего больше

Pointer1 указывает на Node1 V1 = 1
Pointer2 указывает на Node2 V2 = 2
while (not Null) {
if (P1 == P2) {
return есть цикл
} else {
P1 += V1, P2 += V2
}
}

Доказать:
Если есть цикл, то существует время t, когда P1(t) = P2(t)
l — длина цикла
В какой-то момент времени пойнтер P1 будет указывать на один из предыдущих элементов списка:

x = P1(t) = t mod l
z = P2(t) = y + 2t mod l

x - t = k * l
z - y * 2t = m * l

x = t + kl
z = y + 2t + ml

0 = kl - y - t - ml
y + t = (k - m ) / l

y + t = e * l
t = el - y

Если непонятно — теория чисел и модулярная математика :)



Backlinks: