Задача 11: Цикл в связном списке

Что такое связанный список?

Связанный список — это структура данных, в которой элементы (узлы) хранятся в виде цепочки, и каждый узел содержит два компонента:

1. Значение (или данные) — саму информацию, которую хранит узел.
2. Указатель (или ссылку) на следующий узел в списке.

Связанный список состоит из цепочки узлов, где каждый узел указывает на следующий, и последний узел указывает на None (или null в других языках), что обозначает конец списка.

Связанные списки бывают:

• Односвязными — каждый узел указывает только на следующий.
• Двусвязными — каждый узел указывает как на следующий, так и на предыдущий.
• Циклическими — последний узел указывает на первый, создавая цикл.

С помощью связанного списка можно эффективно вставлять и удалять элементы, но доступ к элементам возможен только по порядку, начиная с головы списка.

Условие задачи:

Напишите определение функции def has_cycle(head, pos), которая принимает массив чисел, представляющий элементы связанного списка, и индекс pos, указывающий на элемент, к которому подключен хвост (если pos == -1, то цикла нет). Нужно определить, есть ли цикл в связанном списке.

Возвращайте True, если в списке есть цикл, иначе False.

Пример 1:

Ввод: head = [3, 2, 0, -4], pos = 1
Вывод: True

Пояснение: В данном примере связанный список имеет цикл, потому что последний элемент (-4) указывает на элемент с индексом 1 (значение 2).

3 -> 2 -> 0 -> -4
       ^         |
       |_________|

Пример 2:

Ввод: head = [1, 2], pos = 0
Вывод: True

Пояснение: Связанный список имеет цикл, потому что последний элемент (2) указывает на элемент с индексом 0 (значение 1).

1 -> 2
^     |
|_____|

Пример 3:

Ввод: head = [1], pos = -1
Вывод: False

Пояснение: Связанный список не имеет цикла, потому что последний элемент не указывает на какой-либо другой элемент.

1