#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
bool hasCycle(ListNode* head) {
if (!head || !head->next) {
return false;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (!fast || !fast->next) {
return false;
}
slow = slow->next;
fast = fast->next->next;
}
return true;
}
int main() {
// Example usage:
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(0);
head->next->next->next = new ListNode(-4);
head->next->next->next->next = head->next; // Cycle formed
bool hasCycleResult = hasCycle(head);
std::cout << (hasCycleResult ? "The linked list has a cycle." : "The linked list does not have a cycle.") << std::endl;
// Clean up
ListNode* current = head;
while (current != nullptr) {
ListNode* next = current->next;
delete current;
current = next;
}
return 0;
}