Алгоритм определения наличия цикла в связанном списке

Итак, я недавно столкнулся с алгоритмом, чтобы определить, существует ли цикл в связанном списке. Коды следующие:

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" такое что указанное выше уравнение разрешимо?


person Zhengyang Fang    schedule 06.10.2016    source источник
comment
stackoverflow.com/q/2936213/1835769   -  person displayName    schedule 06.10.2016
comment
правильно ли уравнение, если цикл не начинается с первого узла? например: 1- ›2, 2-› 3, 3- ›4, 4-› 5, 5- ›3, цикл = {3,4,5,3}   -  person shole    schedule 06.10.2016
comment
Любой t = 0 mod a решает 2t = t mod a. Вам также понадобится t >= s, где для входа в цикл требуется s шага.   -  person Matt Timmermans    schedule 06.10.2016
comment
@MattTimmermans ммммм ... Я думаю, может быть, это то же самое после того, как я немного подумаю: 2t -s = t-s (a), поэтому 2t = t (a), хотя не уверен   -  person shole    schedule 06.10.2016
comment
@shole, вам нужны оба условия. Если для входа в цикл длиной 10 требуется 13 шагов, то указатели встретятся при t = 20 и t = 30, но не при t = 10.   -  person Matt Timmermans    schedule 06.10.2016
comment
@MattTimmermans Ага, ты прав   -  person shole    schedule 06.10.2016


Ответы (2)


Ты на правильном пути! Подсказка: что происходит с вашей формулой после а итераций?

person Aasmund Eldhuset    schedule 06.10.2016

Предполагая, что оба указателя начинаются в одной и той же точке цикла (и это не считается встречей)

2t = t (a)

=> 2t - t = 0 (a)

=> t = 0 (a)

что означает, что при t = a * k оба указателя встретятся в начальной точке после того, как прошедшее время будет кратно длине цикла.

Это верно для всех a >= 2, потому что, когда время равно k*a для всех k>1, медленный указатель точно выполняет k циклов, в то время как быстрый указатель работает вдвое быстрее, поэтому он выполняется длиной 2k циклов, но они встречаются в той же точке, которая является отправная точка.

person shole    schedule 06.10.2016
comment
Я заблудился на втором этапе: (как получить 2t - t = 0 (a) из 2t = t (a)? - person Zhengyang Fang; 10.10.2016
comment
Просто минус t% с обеих сторон? - person shole; 11.10.2016