Обнаружение цикла в связанном списке: исчерпывающая теория

Question

Это НЕ проблема обнаружения цикла в связанном списке с использованием известного метода Hare and Tortoise.

В методе Hare & Tortoise у нас есть указатели, работающие на скорости 1x и 2xчтобы определить, что они встречаются, и я убежден, что наиболее эффективным способом и порядком поиска такого типа является O (n).

Проблема в том, что мне нужно придумать доказательство (доказательство или опровержение).) что возможно, что два указателя будут всегда встречаться, когда скорость перемещения равна Ax (A x) и Bx (B x), а A не равно B. Где A a B - два случайных целых числа, работающих в связанном спискес присутствующим циклом.

Это было задано в одном из интервью, которые я недавно посещал, и я не смог доказать себе всесторонне, возможно ли вышеизложенное.Любая помощь приветствуется.

Answer 1

Предположим, что есть петля, скажем, длины L.

Сначала простой случай

Чтобы упростить задачу, сначала рассмотрим случай, когда две частицы целиком зацикливаются одновременно. Эти частицы находятся в одном и том же положении всякий раз, когда n*A = n*B (mod L) для некоторого положительного целого числа n, которое является числом шагов, пока они не встретятся снова. Взятие n=L дает одно решение (хотя может быть и меньшее решение). Таким образом, после L единиц времени частица A совершила A обхода цикла, чтобы вернуться в начало, а частица B совершила B обхода цикла, чтобы вернуться в начало, где они счастливо сталкиваются.

Общий случай

Теперь, что происходит, когда они не входят в цикл одновременно? Пусть A будет более медленной частицей, т.е. A<B, и предположим, что A входит в цикл в момент времени m, и давайте назовем позицию, в которой A входит в цикл 0 (так как они находятся в Цикл, они никогда не могут выйти из него, поэтому я просто переименовываю позиции, вычитая A*m, расстояние A прошло после m единиц времени). Затем в это время B уже находится в позиции m*(B-A) (это реальная позиция после m единиц времени, равная B*m, и поэтому ее переименованная позиция равна B*m-A*m). Затем нам нужно показать, что есть время n такое, что n*A = n*B+m*(B-A) (mod L). То есть нам нужно решение модульного уравнения

(n+m) * (A-B) = 0 (mod L)

Принимая n = k*L-m за k достаточно большим, чтобы k*L>m добился цели, хотя, опять же, может быть меньшее решение.

Поэтому да, они всегда встречаются.

Answer 2

Если ваши два размера шага имеют общий множитель x: скажем, размеры шага - Ax и Bx, тогда просто рассмотрите последовательность, которую вы получите, взяв исходную последовательность и взяв каждый x-й элемент.Эта новая последовательность имеет цикл в том и только в том случае, если исходная последовательность имеет, и выполнение шагов размера A и B на нем эквивалентно выполнению шагов размера Ax и Bx в исходной последовательности.

Это сокращение означает, чтодостаточно доказать, что алгоритм работает, когда A и B взаимно просты.

Answer 3

Гипотеза неверна.Например, если оба указателя совершают скачки четного размера, цикл также имеет четный размер, а расстояние между указателями нечетное, они никогда не встретятся.

UPD это, очевидно, невозможная ситуация.Поскольку два указателя начинаются в одной и той же точке, расстояние между ними всегда будет четным.