141. Цикл в связанном списке (Linked List Cycle)

Задание.

Получен head, заголовок связанного списка.

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

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

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

Пример 1.

Входные данные: head = [3,2,0,-4], pos = 1

Результат: true

Объяснение: В связанном списке есть цикл, где хвост соединяется с 1-м узлом (с индексом 0).

Пример 2.

Входные данные: head = [1,2], pos = 0

Результат: true

Объяснение: В связанном списке есть цикл, где хвост соединяется с 0-м узлом.

Пример 3.

Входные данные: head = [1], pos = -1

Результат: false

Объяснение: В связанном списке нет циклов.

Решение.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(head == NULL)
            return false;

        ListNode *fast = head;
        ListNode *slow = head;

		// пока указатели fast and fast-> next не достигнут пустого элемента
		// будем увеличивать указатель fast на 2 шага, а указатель slow на один
        while(fast != NULL && fast ->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;

			// Если медленный и быстрый указатели свопали,
			// Значит связанный список имеет цикл.
            if(fast == slow)
                return true;
        }

		// если при проходе по списку дошли до пустого элемента, значит в списке нет циклов
        return false;
    }
};

Способ решения.

Для нахождения циклов в списке используется алгоритм Флойда (или алгоритм черепахи и зайца).

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

Заяц бежит впереди черепахи.

На следующем шаге заяц ещё быстрее убегает от черепахи.

Но если в списке есть цикл, когда-нибудь указатели совпадут.