#Hash Table#Linked List#Two Pointers
Дан head заголовок связанного списка. Определите, есть ли в связанном списке цикл.
Цикл в связанном списке есть, если в списке есть некоторый узел, к которому можно снова прийти, непрерывно следуя next указателю. Внутри pos используется для обозначения индекса узла, next к которому подключен указатель tail. Обратите внимание, что pos не передается как параметр .
Верните, true если в связанном списке есть цикл . В противном случае верните false.
Пример 1:
Вход: head = [3,2,0,-4], pos = 1
Выход: true
Пояснение: В связанном списке есть цикл, где хвост соединяется с 1-м узлом (индексированным как 0).
Пример 2:
Вход: head = [1,2], pos = 0
Выход: true
Пояснение: В связанном списке есть цикл, где хвост соединяется с 0-м узлом.
Пример 3:
Вход: head = [1], pos = -1
Выход: false
Пояснение: В связанном списке нет цикла.
Ограничения:
- Количество узлов в списке находится в диапазоне .[0, 104]
- -105 <= Node.val <= 105
- pos является -1действительным индексом в связанном списке.
Продолжение: Можете ли вы решить эту задачу, используя O(1)(т.е. постоянную) память?
Пример решения на go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func hasCycle(head *ListNode) bool {
check := make(map[*ListNode]bool)
for head != nil {
if check[head] {
return true
}
check[head] = true
head = head.Next
}
return false
}