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

Это НЕ задача об обнаружении цикла в связном списке с помощью знаменитого метода "зайца и черепахи".

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

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

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

7
задан bragboy 18 December 2011 в 12:12
поделиться