Учитывая head
, заголовок связанного списка, определите, есть ли в связанном списке цикл.
В связанном списке есть цикл, если в списке есть некоторый узел, к которому можно снова обратиться, непрерывно следуя указателю next
. Внутри pos
используется для обозначения индекса узла, к которому подключен указатель tail next
. Обратите внимание, что pos
не передается в качестве параметра.
Вернуть true
, если в связанном списке есть цикл. В противном случае вернуть false
.
Пример 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).
Пример 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.
Пример 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Как всегда, следите за комментариями к каждой строке.
В этом решении временная сложность равна O(n), так как мы проходим по связному списку только один раз. А пространственная сложность — O(1), потому что мы используем только 2 значения для всего связанного списка.
Судя по моим комментариям к коду, если у вас есть какие-либо вопросы или комментарии, не стесняйтесь обращаться к нам.