Найти цикл в односвязном списке

task69.cpp

#include <iostream>

template <typename T>
struct Node
{
	Node() = default;
	Node(const T& data) : m_data(data) {}

	T data() { return m_data; }
	Node* next() { return m_next.get(); }

	void linkTo(Node* node) { m_next.reset(node); }

private:
	T m_data = default(T);
	std::shared_ptr<Node> m_next = nullptr;
};

template <typename T>
bool HasCycle(Node<T>* head)
{
	auto p = head;
	auto q = head;
	while (p && q && q->next())
	{
		p = p->next();
		q = q->next()->next();
		if (p == q)
			break;
	}

	p = head;
	while (p && q && p != q)
	{
		p = p->next();
		q = q->next();
	}

	if (p && q)
	{
		std::cout << "There's a cycle beginning at lmnt " << p->data() << ".\n";
		return true;
	}
	
	std::cout << "There's no cycle.\n";
	return false;
}

int main()
{
	auto head = new Node<int>{ 0 };
	head->linkTo(new Node<int>{ 1 });
	head->next()->linkTo(new Node<int>{ 2 });
	head->next()->next()->linkTo(new Node<int>{ 3 });
	head->next()->next()->next()->linkTo(new Node<int>{ 4 });

	head->next()->next()->next()->next()->linkTo(head->next()->next());

	HasCycle(head);

	return 0;
}

task69.txt

	Ход решения:
		Заводим два указателя. Первый двигаем по списку с шагом в один элемент, второй - с шагом в два элемента.
		Если в списке есть цикл, то второй указатель рано или поздно догонит первый сзади.

		Важный момент - указатели встретятся не в начале цикла, а где-то на петле цикла.
		Чтобы узнать, где начинается цикл, надо запустить два указателя с одинарным шагом:
		один с головы списка, второй - с момента встречи. Тогда они встретятся как раз в начале цикла.

		0(head) - 1 - 2 - 3 - 4(loop) - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12
					^______________________________________|
		Запускаем два указателя.
		p пройдет по элементам 0, 1, 2, 3, 4,  5,  6, 7, 8, 9.
		q пройдет по элементам 0, 2, 4, 6, 8, 10, 12, 5, 7, 9.
		Они встретятся на элементе 9 - значит, список содержит цикл.
		Запустим p с головы, а q с элемента 9.
		p пройдет по элементам 0,  1,  2,  3, 4.
		q пройдет по элементам 9, 10, 11, 12, 4.

		Это будет работать всегда.
		Пусть начало цикла находится на расстоянии X элементов от головы.
		Пусть при первом запуске с разными шагами указатели встретились на элементе,
		который разбивает петлю цикла на две полупетли по Y и Z элементов.
		В нашем примере X = 4 (от 0 до 4), Y = 5 (от 4 до 9), Z = 4 (от 9 до 4).

		До первой встречи p пройдет (X + Y) шагов, а q - (X + Y + Z + Y) шагов.
		Учитывая, что шаг q в два раза больше шага p, получаем:
			2(X + Y) = X + Y + Z + Y,
		откуда очевидно, что X = Z.
		Тогда если мы запустим указатель p с головы списка и заставим его пройти X шагов,
		а указатель q с момента встречи и заставим его допройти Z шагов по петле,
		то они встретятся как раз в начале цикла.

		В более общем случае все зависит от размеров петли.
		Указатель q может намотать больше кругов по этой петле до встречи с p.
		Но это ничего не меняет; лишь уравнение преобразовывается к виду:
			2(X + Y) = X + (Y + Z)*K + Y.