#include <iostream>
#include <print>
#include <ranges>
template<typename T>
class ForwardList {
public:
class Node {
public:
Node* next = nullptr;
T value;
};
private:
Node* beforeBegin = new Node();
Node* last = beforeBegin;
public:
Node* const& getBeforeBegin() const {
return this->beforeBegin;
}
Node* const pushBack(T&& element) {
auto newNode = new Node();
newNode->value = element;
this->last->next = newNode;
this->last = newNode;
return newNode;
}
Node* const pushBack(T&& element, Node* const& next) {
auto newNode = new Node();
newNode->value = element;
this->last->next = newNode;
this->last = newNode;
this->last->next = next;
return newNode;
}
Node* const oneSpecifcLoopNode() const {
auto slowIt = beforeBegin;
auto fastIt = beforeBegin;
while (true) {
slowIt = slowIt->next;
fastIt = fastIt->next;
if (!fastIt) break;
fastIt = fastIt->next;
if (!fastIt) break;
if (slowIt == fastIt) break;
}
return fastIt;
}
class FirstLoopNodeResult {
public:
Node* const firstLoopNode;
int lengthUntilLoop;
};
std::optional<FirstLoopNodeResult> firstLoopNode() const {
auto loopIt = oneSpecifcLoopNode();
if (!loopIt) return {};
auto listIt = beforeBegin;
int lengthUntilLoop = 0;
while (listIt != loopIt) {
listIt = listIt->next;
loopIt = loopIt->next;
++lengthUntilLoop;
}
return {{
.firstLoopNode = listIt,
.lengthUntilLoop = lengthUntilLoop,
}};
}
};
int main() {
auto list = ForwardList<int>();
list.pushBack(1);
list.pushBack(2);
auto node3 = list.pushBack(9);
list.pushBack(4);
list.pushBack(5);
list.pushBack(11);
list.pushBack(10);
list.pushBack(8, node3);
auto result = list.firstLoopNode();
std::println("firstLoopNode: {}", result->firstLoopNode->value);
std::println("lengthUntilLoop: {}", result->lengthUntilLoop);
}