请设计一个C语言算法,给一个链表的头结点head,判断链表中是否有环
时间: 2024-09-26 17:05:40 浏览: 41
算法:给定一个链表,判断链表中是否存在环
要检测一个链表中是否存在环,可以使用Floyd's Tortoise and Hare (龟兔赛跑) 或者叫快慢指针的方法。这是一种非常高效的解决方案,因为它可以在O(n)的时间复杂度内完成,其中n是链表的长度。
以下是使用C语言编写的基本算法:
```c
#include <stdbool.h>
#include <stdio.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建新节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 检查链表是否存在环
bool hasCycle(ListNode* head) {
if (head == NULL || head->next == NULL) {
return false; // 链表为空或只有一个元素,无环
}
ListNode* slow = head; // 缓慢指针
ListNode* fast = head->next; // 快速指针
while (slow && fast && fast->next) { // 当两指针都有效时
slow = slow->next; // 慢慢移动一步
fast = fast->next->next; // 快速移动两步
if (slow == fast) { // 如果快慢相遇,则有环
return true;
}
}
return false; // 如果遍历结束仍未相遇,说明无环
}
int main() {
// 实际链表创建和测试代码应在这里
ListNode* head = ...;
bool cycleExist = hasCycle(head);
if (cycleExist) {
printf("链表中有环\n");
} else {
printf("链表中无环\n");
}
return 0;
}
```
阅读全文