Обнаружение начала цикла в списке односвязных ссылок?

Question

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

Answer 1

1. обнаружение петли
2. скопировать адрес каждого элемента в набор. Если найден дубликат, это начало цикла

Answer 2

1. Действуйте как обычно, чтобы найти петлю. то есть. Имейте два указателя, увеличивайте один за один шаг, а другой за два шага. Если они оба встретятся через некоторое время, есть цикл.

2. Держите один из указателей фиксированным, чтобы получить общее количество узлов в цикле, скажем L.

3. Теперь с этой точки (увеличьте второй указатель на следующий узел в цикле) в цикле переверните связанный список и посчитайте количество пройденных узлов, скажем, X.

4. Теперь используя второй указатель (цикл прерывается) из той же точки в цикле, просмотрите связанный список и посчитайте количество оставшихся узлов, скажем, Y

5. Цикл начинается после ((X + Y) -L) \ 2 узлов. Или он начинается с (((X + Y) -L) \ 2 + 1) -го узла.

Answer 3

1. Действуйте как обычно, чтобы найти петлю. то есть. Имейте два указателя, увеличивайте один за один шаг, а другой за два шага. Если они оба встретятся через некоторое время, есть цикл.

2. Держите один из указателей фиксированным, чтобы получить общее количество узлов в цикле, скажем L.

3. Теперь с этой точки (увеличьте второй указатель на следующий узел в цикле) в цикле переверните связанный список и посчитайте количество пройденных узлов, скажем, X.

4. Теперь используя второй указатель (цикл прерывается) из той же точки в цикле, просмотрите связанный список и посчитайте количество оставшихся узлов, скажем, Y

5. Цикл начинается после ((X + Y) -L) \ 2 узлов. Или он начинается с (((X + Y) -L) \ 2 + 1) -го узла.

Answer 4

Я слышал этот точный вопрос как вопрос викторины.

Самое элегантное решение:

Поместите оба указателя на первый элемент (назовите их A и B)

Тогда продолжайте цикл ::

• Переход A к следующему элементу
• Переходите к следующему элементу снова
• Переход B к следующему элементу

Каждый раз, когда вы обновляете указатель, проверьте, идентичны ли A и B. Если в какой-то момент указатели A и B идентичны, то у вас есть цикл. Проблема с этим подходом состоит в том, что вы можете в конечном итоге перемещаться по циклу дважды, но не более, чем дважды с указателем A

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

Наиболее эффективный способ сделать это с большей памятью - это поместить указатели на элементы в массиве, отсортировать их, а затем искать повтор.