Linked List Cycle

Условие

Дана голова односвязного списка, нужно определить, есть ли в списке цикл. Цикл возникает, если какой-либо узел в списке ссылается на один из предыдущих узлов, образуя петлю. Функция должна вернуть true, если цикл существует, и false в противном случае.

Примеры

Input: head = [3, 2, 0, -4], pos = 1

Output: true

Explanation: В этом списке цикл, так как хвост ссылается на второй узел.

Input: head = [1, 2], pos = 0

Output: true

Explanation: Хвост ссылается на первый узел, образуя цикл.

Input: head = [1], pos = -1

Output: false

Explanation: В списке нет цикла.

Решение

// Определение структуры узла связанного списка
class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

// Функция для определения, есть ли цикл в связанном списке
fun hasCycle(head: ListNode?): Boolean {
    // Используем два указателя - медленный (slow) и быстрый (fast)
    var slow = head
    var fast = head
    
    // Пока быстрый указатель и следующий за ним не равны null
    while (fast != null && fast.next != null) {
        slow = slow?.next           // Медленный указатель перемещается на 1 узел
        fast = fast.next?.next      // Быстрый указатель перемещается на 2 узла
        
        // Если указатели встретились, значит есть цикл
        if (slow == fast) {
            return true
        }
    }
    
    // Если цикл не найден, возвращаем false
    return false
}

Временная сложность

Временная сложность решения — O(n), где n — количество узлов в связанном списке. В худшем случае нам нужно пройти по всем узлам списка один раз.

Пространственная сложность

Пространственная сложность — O(1). Мы используем два указателя (slow и fast), что требует константного дополнительного пространства.