题目
给你一个链表的头结点判断链表中是否有环,如果有返回TRUE,否则返回FALSE。
算法设计
我们要排除用遍历,因为一旦链表中有环,遍历会陷入死循环。
这道题可以用快慢指针,slow一次走一步,fast一次走两步,当slow=fast时就证明链表中有环。
证明如下:
fast先进环,slow后进环。slow进环时与fast的距离为n。slow进环后fast开始追击,每一次移动slow走一步,fast走两步n–,当n=0时fast和slow就相遇了。
代码实现
/**
* 函数 HasCycle 用于判断给定链表是否存在循环
*
* @param head 链表的头节点指针
* @return 如果存在循环则返回 true,否则返回 false
*/
bool HasCycle(struct ListNode* head) {
struct ListNode* slow = head; // 定义慢指针,初始指向头节点
struct ListNode* fast = head; // 定义快指针,初始也指向头节点
while (fast && fast->next) { // 当快指针和它的下一个节点都不为空时进行循环
slow = slow->next; // 慢指针向后移动一步
fast = fast->next->next; // 快指针向后移动两步
if (slow == fast) { // 如果慢指针和快指针相遇,说明存在循环
return true;
}
}
return false; // 如果没有遇到循环,返回 false
}