Алгосы от Влада, часть 3. Быстрый и медленный указатель

Опубликовано 01.02.2024

Автор Крыловский Владислав 4 мин. чтения

Введение
Скользящее окно
Два указателя или итератор
Быстрый и медленный указатель
Мерж интервалов
Циклическая сортировка
Инвертирование связанного списка на месте
Дерево BFS
Дерево DFS
Две кучи
Подмножества
Модифицированный бинарный поиск
Побитовый XOR
Лучшие элементы К (top K elements)
k-образный алгоритм слияния (K-Way merge)
0 or 1 Knapsack (Динамическое программирование)
Топологическая сортировки

Введение

Подход с использованием указателей Fast & Slow, также известный как алгоритм “заяц и черепаха”s, - это алгоритм с использованием двух указателей, которые перемещаются по массиву (или последовательности/LinkedList) с разной скоростью. Этот подход весьма полезен при работе с циклическими LinkedList’ами или массивами.

Двигаясь с разной скоростью (скажем, в циклическом LinkedList), алгоритм доказывает, что два указателя обязательно встретятся. Быстрый указатель должен догнать медленный, как только оба указателя окажутся в замкнутом цикле.

Одной из известных задач, решенных с помощью этой техники, был “Поиск цикла в LinkedList”. Давайте рассмотрим эту задачу, чтобы понять принцип Fast & Slow.

Постановка задачи

Задав голову односвязного списка LinkedList, напишите функцию, определяющую, есть ли в LinkedList цикл или нет.

Решение

Представьте себе двух гонщиков, бегущих по круговой гоночной трассе. Если один гонщик быстрее другого, то он обязательно догонит и обойдет медленного гонщика сзади. Мы можем использовать этот факт, чтобы разработать алгоритм для определения того, есть ли в LinkedList цикл или нет.

Представьте, что у нас есть медленный и быстрый указатели для обхода LinkedList. На каждой итерации медленный указатель перемещается на один шаг, а быстрый - на два. Это дает нам два вывода:

Если в LinkedList нет циклов, то быстрый указатель достигнет конца LinkedList раньше медленного указателя и покажет, что в LinkedList нет циклов.
Медленный указатель никогда не сможет догнать быстрый указатель, если в LinkedList нет цикла.

Если LinkedList имеет цикл, то сначала в цикл попадает быстрый указатель, а затем медленный. После этого оба указателя будут двигаться по циклу бесконечно. Если на каком-то этапе оба указателя встретятся, можно сделать вывод, что в LinkedList есть цикл. Давайте проанализируем, возможна ли встреча двух указателей. Когда быстрый указатель приближается к медленному сзади, у нас есть две возможности:

Быстрый указатель отстает от медленного на один шаг.
Быстрый указатель отстает от медленного на два шага.

Все остальные расстояния между быстрым и медленным указателями будут сводиться к одной из этих двух возможностей. Давайте проанализируем эти сценарии, считая, что быстрый указатель всегда перемещается первым:

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

Код

Вот как будет выглядеть наш алгоритм:

  
package main

import "fmt"

type Node struct {
  Value int
  Next  *Node
}

func hasCycle(head *Node) bool {
  slow, fast := head, head
  for fast != nil && fast.Next != nil {
    fast = fast.Next.Next
    slow = slow.Next
    if slow == fast {
      return true // found the cycle
    }
  }
  return false
}

func main() {
  head := &Node{Value: 1}
  head.Next = &Node{Value: 2}
  head.Next.Next = &Node{Value: 3}
  head.Next.Next.Next = &Node{Value: 4}
  head.Next.Next.Next.Next = &Node{Value: 5}
  head.Next.Next.Next.Next.Next = &Node{Value: 6}
  
  fmt.Printf("LinkedList has cycle: %t\n", hasCycle(head))
  
  head.Next.Next.Next.Next.Next.Next = head.Next.Next
  fmt.Printf("LinkedList has cycle: %t\n", hasCycle(head))
  
  head.Next.Next.Next.Next.Next.Next = head.Next.Next.Next
  fmt.Printf("LinkedList has cycle: %t\n", hasCycle(head))
}

Вывод :

LinkedList has cycle: false
LinkedList has cycle: true
LinkedList has cycle: true

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

Как мы выяснили выше, как только медленный указатель войдет в цикл, быстрый указатель встретится с медленным указателем в том же цикле. Поэтому временная сложность нашего алгоритма будет равна \(O(N)\) где \(N\) - общее количество узлов в LinkedList.

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

Алгоритм работает в постоянном пространстве \(O(1)\).