Учитывая head, заголовок связанного списка, определите, есть ли в связанном списке цикл.
В связанном списке есть цикл, если в списке есть некоторый узел, к которому можно снова обратиться, непрерывно следуя указателю next. Внутри pos используется для обозначения индекса узла, к которому подключен указатель хвоста next. Обратите внимание, что pos не передается в качестве параметра.
Вернуть true, если в связанном списке есть цикл. В противном случае вернуть false.
Пример 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Решение:
В данной задаче мы должны проверить, присутствует ли какой-либо цикл в связанном списке.
Мы решим это методом двух указателей. Во-первых, мы сделаем два указателя: медленный и быстрый. медленныйуказатель будет увеличен на одну позицию, а быстрыйуказатель будет увеличен на две позиции.
ListNode* slow = head; ListNode* fast = head;
Теперь мы проверим, пуст ли список, и если да, то вернем false, так как в списке не будет цикла без элементов.
if(head == NULL)
return false;
Следующим шагом является обход списка до тех пор, пока быстрыйуказатель не достигнет null или конца списка. медленный и быстрыйуказатель будут увеличены на одну и две позиции соответственно.
При обходе мы должны проверить, равны ли медленный и быстрыйуказатель, тогда мы вернем true. Если оба указателя равны, то ясно, что список содержит цикл.
while(fast != NULL && fast -> next != NULL)
{
slow = slow -> next;
fast = fast -> next -> next;
if(slow == fast)
return true;
}
В противном случае вернуть ложь.
Ниже приведен полный код данной проблемы:
Спасибо за прочтение!
S.
