Итак, я недавно столкнулся с алгоритмом, чтобы определить, существует ли цикл в связанном списке. Коды следующие:
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null) {
if (fast.next == null) {
return false;
}
if (fast.next == slow) {
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
Пытаясь доказать правильность этого алгоритма, я пришел к мысли: предположим, что периметр цикла равен «a», время, прошедшее до встречи двух указателей, равно «t». Поскольку скорость «быстрого» узла в два раза выше, чем «медленного» узла, мы можем получить математическое соотношение:
2t mod a = t mod a
Теперь "a" - это константа, представляющая периметр, а "t" может быть 1,2,3 .... Тогда как мне доказать, что независимо от того, какое значение "a", мы всегда можем найти "t" такое что указанное выше уравнение разрешимо?
t = 0 mod a
решает2t = t mod a
. Вам также понадобитсяt >= s
, где для входа в цикл требуетсяs
шага. - person Matt Timmermans   schedule 06.10.2016