Цикл связного списка

Задача Leetcode: Цикл связного списка

Задача:

Дана head, глава связанного списка, определить, есть ли в этом связанном списке цикл.

Цикл в связанном списке существует, если в списке есть некоторый узел, до которого можно добраться, постоянно следуя за следующим указателем. Внутри, pos используется для обозначения индекса узла, с которым связан следующий указатель tail. Обратите внимание, что pos не передается в качестве параметра.

Возвращает true, если в связном списке есть цикл. В противном случае возвращается false.

Шаблон: Техника двух указателей

Подход:

1. Краевой случай: Если входное значение равно null, то список пуст, поэтому цикла не существует.
2. Создайте два указателя, оба начинаются с head. Один указатель движется медленно, а другой — в два раза быстрее.
3. Если более медленный указатель догоняет более быстрый, верните true, так как цикл существует.
4. Если более быстрый указатель достигает нуля, то возвращается false, так как цикла нет.

Нотация Big-O:

Временная сложность: O(n)
Мы выполняем итерацию n раз для каждого элемента.

Сложность пространства: O(1)
Мы не используем никаких дополнительных структур данных для хранения.

Код:

public class Solution {
    public boolean hasCycle(ListNode head) {

        if(head == null){
            return false;
        }

        ListNode slow = head; 
        ListNode fast = head;

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;

            if(slow == fast){
                return true;
            }
        }
        return false;
    }
}