Кодирование паттернов интервью — III
Быстрые и медленные указатели — это метод, используемый для решения проблем программирования, связанных с обходом связанного списка, включая, помимо прочего, следующее.
- Цикл связанного списка
- Середина LinkedList
- Связанный список палиндромов
Предварительные условия
Эти предварительные условия помогают определить, что проблема может быть решена с помощью метода быстрых и медленных указателей.
- Нам предоставляется связанный список для работы с
- Мы ищем какое-то свойство вокруг структуры списка или положения определенного элемента (начало/середина/конец списка, цикл в списке или фраза и т. д.).
Алгоритм
Основная идея этого метода заключается в том, что если у нас есть один указатель, перемещающийся вниз по списку на 1 узел за итерацию, а второй указатель перемещается по списку с большей скоростью (2 узла за итерацию), второй указатель в конечном итоге будет вращаться и ловить снова с первым указателем, если в списке есть цикл.
Если цикла нет, второй указатель первым достигнет конца списка и станет нулевым.
Вот основные шаги для реализации быстрых и медленных указателей.
- Создайте два указателя: быстрый и медленный. Пусть slow указывает на первый элемент списка, а fast указывает на второй элемент.
- Повторяйте шаги 3–4, пока не будет найдено состояние решения или один из указателей не станет нулевым.
- Если элемент, на который указывает fast, равен элементу, на который указывает slow, в списке есть цикл (вернуть true, поскольку решение, если это то, что мы ищем).
- В противном случае увеличьте позицию медленно вниз по списку на 1 и быстро вниз по списку на 2.
- Цикл не найден (возвратите false, если это то, что мы ищем).
Пример Kotlin — цикл связанного списка (просто)
Я покажу простой пример поиска цикла в связанном списке с помощью Kotlin.
Задача Связанный список Цикл предоставляет нам заголовок связанного списка, и мы должны вернуть логическое значение true, если список содержит цикл, и false в противном случае.
Я бы сначала позаботился о крайних случаях, когда в списке есть только 1 или 0 элементов. В этих случаях в списке не может быть цикла, и мы можем вернуть false.
Далее мы объявим наши указатели fast и slow. медленныйуказатель будет начинаться с первого элемента, а быстрый указатель будет начинаться со второго.
Теперь я буду повторять цикл while до тех пор, пока значение slow или fast не станет нулевым. В каждой итерации я проверяю, равно ли медленно быстро. Если они равны друг другу, мы нашли цикл и можем вернуть true. В противном случае мы увеличиваем slow на 1 и fast на 2.
Наконец, если мы вышли из цикла, потому что значение slow или fast стало null, в списке нет цикла. Таким образом, мы можем завершить функцию с возвратом false.
Вот и все!
Больше узоров смотрите здесь:
