c++ floyd判圈算法

Floyd判圈算法，也称为Floyd的环检测算法或“龟兔赛跑算法”，是一种用来检测链表或序列中是否存在环的经典算法。它的主要思想是通过两个指针（一个快指针和一个慢指针）来判断链表中是否有环。

算法原理

• 设定两个指针：一个快指针（每次移动两步）和一个慢指针（每次移动一步）。
• 如果链表中存在环，快指针最终会追上慢指针，因为在环中，快指针走的步数是慢指针的两倍。
• 如果快指针走到链表末尾，说明链表中没有环。

算法步骤

1. 初始化两个指针，slow 和 fast，都指向链表的头节点。
2. 快指针fast每次移动两步，慢指针slow每次移动一步。
3. 如果slow和fast相遇，则说明链表中有环。
4. 如果fast指针为空或者fast的下一个节点为空，说明链表中没有环。

示例

#include <iostream>
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};// Floyd判圈算法
bool hasCycle(ListNode *head) {if (head == nullptr) return false;  // 空链表没有环ListNode *slow = head;ListNode *fast = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;          // 慢指针每次走一步fast = fast->next->next;    // 快指针每次走两步if (slow == fast) {         // 如果慢指针和快指针相遇，则有环return true;}}return false;  // 快指针走到链表末尾，表示没有环
}int main() {// 创建一个链表: 1 -> 2 -> 3 -> 4 -> 5ListNode *head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);// 创建一个环: 5 -> 2head->next->next->next->next->next = head->next;if (hasCycle(head)) {cout << "链表中有环" << endl;} else {cout << "链表中没有环" << endl;}return 0;
}

• 时间复杂度：O(n)，其中n是链表中的节点数。因为快指针和慢指针最多会遍历链表一次，所以时间复杂度是线性的。
• 空间复杂度：O(1)，因为算法只使用了常数空间（即两个指针），不依赖于链表的大小。