本文主要是介绍单向环形链表的创建与判断链表是否有环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
单向环形链表的创建与单向链表的不同在于，最后一个节点的next需要指向头结点；
判断链表是否带环，只需要使用两个指针，一个步长为1，一个步长为2，环状链表这两个指针总会相遇。
如下示例代码：
list.h
#ifndef LIST_H__
#define LIST_H__typedef struct _listNode {int data;struct _listNode *next;
}listNode_t;typedef struct _list {int size;listNode_t *head;
}list_t;
#endif
list.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list.h"list_t *listCreate(void)
{list_t *list = (list_t *)malloc(sizeof(list_t));if(list == NULL) {perror("malloc :");exit(-1);}list->size = 0;list->head = NULL;return list;
}int listInsertHead(list_t *list, int dat)
{listNode_t *pNode = (listNode_t *)malloc(sizeof(listNode_t));if(pNode == NULL) {perror("malloc :");exit(-1);}pNode->data = dat;pNode->next = NULL;listNode_t *headNode = list->head;if(headNode == NULL) {list->head = pNode;pNode->next = list->head; //pNode作为头结点，同时pNode的next指向头结点，构成环状} else {pNode->next = list->head; //在头部插入新的节点//找到末尾的节点，将末尾节点的next指向新的节点。while(headNode->next != list->head) {headNode = headNode->next;}headNode->next = pNode;//头结点指向新的节点list->head = pNode;}list->size ++;return 0;
}
bool listIsLoop(list_t *list)
{//如果链表是环状的，fast和slow总会相遇listNode_t *fast = list->head;listNode_t *slow = list->head;if(list->head == NULL || list->head->next == NULL) {return false;}while(fast->next->next != NULL || slow->next != NULL) {if(fast == slow) {return true;}}return false;
}void listDump(list_t *list)
{listNode_t *temp = list->head;//这里可以验证链表是不是环状的，将size改为两倍大小，看是否循环输出while(list->size) {printf("%d-> ", temp->data);temp = temp->next;list->size --;}printf("\n");return ;
}
int main()
{list_t *list = listCreate();for(int i = 0; i < 5; i++) {listInsertHead(list, i);}listDump(list);printf("list %s loop\n", listIsLoop(list)? "is" : "is not" );return 0;
这篇关于单向环形链表的创建与判断链表是否有环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
