Односвязный список. Замкнулся или нет?

[EUgeneUS]

По легенде, эту задачу давали на собеседованиях в Майкрософте в середине 90-х.

Есть односвязный список любой длины. Список может закончиться (последний элемент указывает на null), либо замкнуться на себя в любое место (последний элемент указывает на какой-то элемент списка, может быть на самого себя).
Предложить алгоритм, который за время не хуже чем O(n) даст ответ на вопрос: список закончился или замкнулся?
Нельзя создавать никакие динамические структуры данных: в распоряжении есть только некоторое количество переменных, количество которых не зависит от длины списка.

[Pphantom]

Неоптимальное, кажется, решение, но в $O(n)$ вписывается. Берем два взаимно простых числа $p$ и $q$ и, стартовав с одного элемента, смещаемся по списку двумя указателями: одним на $p$ элементов, вторым - на $q$. Если в один прекрасный момент мы любым из них наткнемся на null - ответ очевиден; если в какой-то момент два указателя будут указывать на одно и то же - список имеет цикл. По идее, в среднем наилучший результат обеспечит пара $(1,2)$, но для конкретных циклов быстрее может оказаться и какая-то другая.

[EUgeneUS]

Решение, понятно, верное. И единственное мне известное. В O(n) укладывается.
А меньше, чем за O(n) проверить невозможно, так как нужно проверить каждый элемент, куда ссылается.

[Pphantom]

EUgeneUS в сообщении #1176407 писал(а):

А меньше, чем за O(n) проверить невозможно, так как нужно проверить каждый элемент, куда ссылается.

Асимптотику сделать меньше, естественно, нельзя, но, возможно, получится уменьшить константу, хотя, кажется, менее чем двумя обходами списка не обойтись, если память лимитирована.

[EUgeneUS]

Можно прикинуть.

Пусть сдвиг указателя на следующий элемент стоит столько же сколько сравнение, для простоты.
Сравнивать надо только положение "быстрого" указателя, но в каждом узле два раза - с null и со значением "медленного" указателя.
"Быстрый" указатель должен пройти весь список, меньше 3n не получается (на каждом шаге два сравнения и один сдвиг указателя), и уперлись в null. Общие затраты будут строго больше - добавятся затраты на смещение "медленного" указателя.

Рассмотрим два случая:

1. Список замыкается на начало.
а) Отношение скоростей 1:2. Затраты: 6n + n = 7n.
б) Отношение скоростей большое. Затраты: 3n (быстрый успевает обойти список и упереться в медленный)

2. Список замыкается на последний элемент.
а) Отношение скоростей 1:2. Затраты: 6n + n = 7n.
б) Отношение скоростей большое, обозначим его как V. Затраты: 3Vn + n

То есть при отношении 1:2 получаем результат за время зависящее от длины списка, как O(n), но слабо зависящее от его конфигурации.
При другом отношении время начинает сильно зависеть от конфигурации списка, впрочем продолжая оставаться O(n).

[Nemiroff]

Если список не нужно сохранять, то можно сделать его реверс. Если придём к начальному элементу, то есть цикл.

[EUgeneUS]

Nemiroff
Забавное решение.
В приведенной формулировке - подходящее. В более жесткой ("нельзя метить элементы списка, в том числе с помощью новых структур данных") - нет.

За длительное время, которое подсовываю эту задачку, наверное, первая успешная попытка "пометить" элементы списка без дополнительной памяти.

[_Ivana]

Простите, не могли бы вы объяснить решение? Вот, к примеру, есть список

Используется синтаксис Haskell

l = (1+) : l

Как написать тестирующую функцию, проверяющую условие задачи?

[EUgeneUS]

Цитата:

Используется синтаксис Haskell

К сожалению ничем не могу помочь
И не ясно, какое решение из двух нужно объяснить.

[_Ivana]

Тогда может объясните, какое отношение к абстракции односвязного списка имеют понятия "указатель", "указывать на одно и то же" и т.п.

[EUgeneUS]

_Ivana

Наверное никакое. Если честно, тонкая разница между указателем и ссылкой регулярно ускользает от меня.
Если Вам это режет глаз. Ну что ж. Есть вариант: возможно, Вам имеет смысл обратиться к модератору для перенесения темы в карантин по четвертому пункту:

Цитата:

4. Недостаточно внятная информация о предмете обсуждения

. Так сказать для приведения в порядок.

[arseniiv]

Насколько я помню, не любой список — односвязный. Вот хаскелевский [a] хотя и реализуется cons-ячейками (когда не оптимизируется в ноль), но, конечно, сравнить две такие ячейки не по значению не получится (если только у GHC нет какой-то тайной магии на этот счёт).

[_Ivana]

EUgeneUS судя по реакции в теме, никому это больше глаз не режет, или все делают необходимые выводы из контекста. Карантин - это лишнее, пусть остается как в ПДД - сначала дается определение понятия "велосипед" без упоминания руля (под которое подходят и роликовые коньки и тележка из супермаркета), а потом идет правило, запрещающее управлять велосипедом не держась за руль...

-- 14.12.2016, 00:46 --

arseniiv в сообщении #1176789 писал(а):

не любой список — односвязный

Хаскелевский, Схемный и многие другие - односвязные.

arseniiv в сообщении #1176789 писал(а):

сравнить две такие ячейки не по значению не получится

Я пытался намекнуть об этом ТС, но безуспешно.

[mihaild]

Тут конфликт обозначений.
Под односвязным список можно понимать функциональное "пустой список ИЛИ пара (элемент, список)". А можно - императивное "Node*, где Node - это пара (элемент, Node*)".
При использовании первого определения проблема не с решением, а уже с постановкой задачи - непонятно, что такое "список замкнулся". Если "для некоторых $n \neq m$ хвосты, начинающиеся с $n$-го и $m$-го элементов совпадают" - то эта задача неразрешима:

Используется синтаксис Python

def get_list(turing_machine, configuration=start_configuration):
  if configuration == end_configuration:
    yield from get_list(turing_machine, start_configuration)
  yield configuration
  yield from get_list(turing_machine, next_configuration(turing_machine, configuration))

get_list(MT) зациклен (по определению про совпадающие хвосты) тогда и только тогда, когда МТ останавливается.

[arseniiv]

_Ivana в сообщении #1176791 писал(а):

Хаскелевский, Схемный и многие другие - односвязные.

Хм, да, передумал, получается, что всё-таки единственная разница в том, есть ли способ узнавать, «где находится» объект (в данном случае cons-ячейка).