Быстрый указатель в алгоритмах.

Допустим, что вам нужно найти середину связного списка, как это быстрее всего сделать? Завести 2 указателя, один будет шагать через один элемент, а второй - по каждому элементу. Таким образом когда первый указатель доберется до конца такого списка - второй будет указывать на середину. Так вот первый указатель называют "быстрым".

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

Node {
  int value;
  Node next;
}

Нам нужно найти ноду в этом графе, которая начинает бесконечный цикл.
Например:

1 -> 2 -> 3 -> 4 -> 2

Тут нода со значением 2 начинает цикл.
Если же ноды нет, то метод должен вернуть null.
Решение этой задачи довольно простое, если бы не одно условие: нужно найти решение без использования дополнительной памяти.
Насколько я помню, я встретил ее по теме "какие задачи не нужно задавать на собесах", т.к. если решения ты не знаешь - решить ее практически невозможно, но все равно - подумайте, ну а вдруг 🙂
p.s: задача была задана на собесе в компанию Apple.

#algorithms #interview