Объясните, как работает поиск начального узла цикла в связанном списке циклов?
В соответствии с спецификациями w3 интерфейс ширины / высоты является unsigned long, поэтому от 0 до 4,294,967,295 (если я помню, что число справа - может быть несколько).
EDIT: Странно, он говорит unsigned long, но это тестирование показывает только нормальное длинное значение как max: 2147483647. Jsfiddle - 47 работает, но до 48 и возвращается к умолчанию.
1 ответ
Это алгоритм Флойда для обнаружения цикла. Вы спрашиваете о второй фазе алгоритма - когда вы нашли узел, который является частью цикла, как найти начало цикла?
В первой части алгоритма Флойда заяц делает два шага за каждый шаг черепахи. Если черепаха и заяц когда-либо встречаются, то существует цикл, и точка встречи является частью цикла, но не обязательно первым узлом цикла.
Когда черепаха и заяц встречаются, мы нашли наименьшее i (количество шагов, сделанных черепахой), такое, что Xi = X2i. Пусть mu - это количество шагов от X0 до начала цикла, а lambda - длина цикла. Тогда i = mu + alambda, а 2i = mu + blambda, где a и b - целые числа, обозначающие, сколько раз черепаха и заяц обошли цикл. Вычитание первого уравнения из второго дает i = (b-a)*lambda, поэтому i - целое число, кратное лямбды. Следовательно, Xi + mu = Xmu. Xi представляет собой точку встречи черепахи и зайца. Если переместить черепаху обратно в начальный узел X0, и позволить черепахе и зайцу продолжать движение с той же скоростью, то после mu дополнительных шагов черепаха достигнет Xmu, а заяц достигнет Xi + mu = Xmu, поэтому вторая точка встречи обозначает начало цикла.