贩毒案链表是否有环C语言
时间: 2023-11-09 17:08:45 浏览: 41
判断一个链表是否有环可以使用快慢指针的方法,具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
// 判断链表是否有环
bool hasCycle(struct ListNode *head) {
if (head == NULL || head->next == NULL) {
return false; // 链表为空或只有一个节点,必然无环
}
struct ListNode *slow = head;
struct ListNode *fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return false; // 快指针到达链表末尾,无环
}
slow = slow->next;
fast = fast->next->next;
}
return true; // 快慢指针相遇,有环
}
int main() {
// 创建链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3(形成一个环)
struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
head->val = 1;
head->next = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next->val = 2;
head->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next->next->val = 3;
head->next->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next->next->next->val = 4;
head->next->next->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next->next->next->next->val = 5;
head->next->next->next->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));
head->next->next->next->next->next->val = 6;
head->next->next->next->next->next->next = head->next->next; // 环的入口是节点 3
// 判断链表是否有环
bool has_cycle = hasCycle(head);
if (has_cycle) {
printf("链表有环\n");
} else {
printf("链表无环\n");
}
return 0;
}
```
输出结果为:
```
链表有环
```