用c语言实现以下要求1、建立如下单链表(与图中完全一致) →A□→B□→C□→D□→E□ L ↖□G←□F↗ 2.判断单链表是否有环,如果有,输出环的入口结点,对上图,即输出C结点。
时间: 2024-12-10 18:45:52 浏览: 22
在C语言中,你可以使用单链表和循环检测算法(也称为快慢指针或龟兔赛跑法)来实现这个需求。首先,我们定义链表节点结构体:
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct Node {
char data;
struct Node* next;
} Node;
// 创建一个链表节点
Node* createNode(char data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 插入节点到链表
void insertNode(Node** head, char data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
}
// 判断链表是否有环
bool hasCycle(Node* head) {
if (head == NULL || head->next == NULL) {
return false;
}
Node* slow = head;
Node* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return false;
}
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
// 如果快指针追上了慢指针,说明有环
return true;
}
// 找到环的入口节点
Node* findCycleStart(Node* head) {
if (!hasCycle(head)) {
return NULL;
}
Node* slow = head;
Node* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
fast = head; // 快速移动到环起点
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
break;
}
}
return slow;
}
int main() {
Node* listHead = NULL;
insertNode(&listHead, 'A');
insertNode(&listHead, 'B');
insertNode(&listHead, 'C');
insertNode(&listHead, 'D');
insertNode(&listHead, 'E');
Node* G = createNode('G');
Node* F = createNode('F');
G->next = F;
F->next = listHead->next; // 将环连接到列表中
Node* cycleStart = findCycleStart(listHead);
if (cycleStart != NULL) {
printf("Cycle detected at node: %c\n", cycleStart->data);
} else {
printf("No cycle detected.\n");
}
return 0;
}
```
这段代码首先创建了一个按照题目描述的单链表,然后检查是否存在环,如果有环则找到环的入口节点。运行这段代码会得到环的入口,也就是上图中的C节点。如果没有环,就会输出"No cycle detected."。
阅读全文