链表中是否有环【c语言】

本文主要是介绍链表中是否有环【c语言】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义两个指针，一个每次跳跃两个节点（快指针），另一个每次跳跃一个节点（慢指针）。如果存在环，他们最终会在环中的某个点相遇。如果链表无环，快指针将先到达链表尾端。

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node, *LinkedList;// 创建一个新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("Error! Unable to create a new node.\n");exit(0);}newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表末尾添加新节点
void append(LinkedList* head, int data) {if (*head == NULL) {*head = createNode(data);}else {Node* lastNode = *head;while (lastNode->next != NULL) {lastNode = lastNode->next;}lastNode->next = createNode(data);}
}// 释放链表内存
void freeList(Node* head)
{}int hasCycle(Node* head)
{if (head->next == NULL){return 0;}Node* slow = head;  //慢指针Node* fast = head;  //快指针while (fast != NULL && fast->next != NULL){fast = fast->next->next;  //快指针每次移动两步slow = slow->next;        //慢指针每次移动一步if (fast == slow)         //如果快慢指针相遇，说明有环。{return 1;}}return 0;
}int main() {// 创建节点Node* head = createNode(1);Node* node2 = createNode(2);Node* node3 = createNode(3);Node* node4 = createNode(4);Node* node5 = createNode(5);//1->2->3->4//      \  ///       5// 构建环形链表head->next = node2;node2->next = node3;node3->next = node4;node4->next = node5;node5->next = node3; // 形成环if (1 == hasCycle(head)){printf("链表有环.\n");}else{printf("链表没有环.\n");}// 释放链表内存//freeList(head);system("pause");return 0;
}