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

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