单向环形链表的创建与判断链表是否有环

        单向环形链表的创建与单向链表的不同在于，最后一个节点的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;