Обнаружение цикла связного списка в JavaScript

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

Учитывая head, заголовок связанного списка, определите, есть ли в связанном списке цикл.

В связанном списке есть цикл, если в списке есть какой-то узел, к которому можно снова добраться, непрерывно следуя за указателем next. Внутри pos используется для обозначения индекса узла, к которому подключен указатель next хвоста. Обратите внимание, что pos не передается в качестве параметра.

Вернуть true , если в связанном списке есть цикл. В противном случае верните false.

Example 1: 
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Ограничения:

• Количество узлов в списке находится в диапазоне [0, 104].
• -105 <= Node.val <= 105
• pos - это -1 или действительный индекс в связанном списке.

Решение 1. Хеширование

1. Просмотрите указанный связанный список и сохраните узлы в объекте Set (), чтобы избежать дублирования значений
2. Если происходит дублирование, связанный список представляет собой цикл, функция возвращает true
3. После обхода, если дублирующийся узел не найден, функция возвращает false

Временная сложность: O (n). Требуется только один обход связанного списка.

Сложность пространства: O (n). n - это пространство, необходимое для хранения узлов в Set ().

Решение 2. Алгоритм Флойда "черепаха и заяц"

1. Пройдите по заданному списку с двумя указателями
2. Медленный указатель перемещается на один, быстрый указатель на два
3. Если два указателя встречаются, возвращает true, если нет - false

Временная сложность: O (n). Требуется только один обход связанного списка.

Сложность пространства: O (1). Место не требуется, оно постоянно.

Ресурсы: