Циклический односвязный список

Циклический односвязный список

Ранее в этой статье я подробно объяснил что такое односвязный список. Сейчас же поговорим про односвязный циклический список.

Циклический список - это тот же односвязный список, где последний элемент списка ссылается на head, т.е. tail.Next = head¹ — таким образом, дойдя до конца, вы можете вернуться снова в начало списка².

Рассмотрим простой пример, который определяет наличие цикла в односвязном списке:

// базовая структура
type ListNode struct 
    Val  int
    Next *ListNode
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    
        // если встретятся, вернем true
        if slow == fast {
            return true
        }
    }
    
    return false
}

В этой задаче для определения цикла я использовал алгоритм "два указателя", реализовав их в виде переменных slow/fast. Один из них двигается на 1 шаг вперед, а 2-ой — на 2 шага вперед. Если будет цикл — они обязательно встретятся друг с другом по условию if slow == fast, а если цикла нет, то условие for отработает и вернется false.

¹ — в прошлой статье мы рассматривали структуру без поля Tail, хотя его лучше использовать, чтобы за О(1) сразу найти конец (зависит, конечно, от задачи). В нашем случае мы решаем задачу без него.

² — если хвост указывает на голову, то все решение выше сводится к "решению в одну строку" — проверкой ссылки хвоста (если указывает на head — есть цикл), но бывают ситуации, когда хвост может указывать не на голову, а на другой элемент списка.