链表中是否有环【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;
}