? ? ? ? 單向環(huán)形鏈表的創(chuàng)建與單向鏈表的不同在于，最后一個(gè)節(jié)點(diǎn)的next需要指向頭結(jié)點(diǎn)；

? ? ? ? 判斷鏈表是否帶環(huán)，只需要使用兩個(gè)指針，一個(gè)步長(zhǎng)為1，一個(gè)步長(zhǎng)為2，環(huán)狀鏈表這兩個(gè)指針總會(huì)相遇。

如下示例代碼：

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作為頭結(jié)點(diǎn)，同時(shí)pNode的next指向頭結(jié)點(diǎn)，構(gòu)成環(huán)狀} else {pNode->next = list->head; //在頭部插入新的節(jié)點(diǎn)//找到末尾的節(jié)點(diǎn)，將末尾節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)。while(headNode->next != list->head) {headNode = headNode->next;}headNode->next = pNode;//頭結(jié)點(diǎn)指向新的節(jié)點(diǎn)list->head = pNode;}list->size ++;return 0;
}
bool listIsLoop(list_t *list)
{//如果鏈表是環(huán)狀的，fast和slow總會(huì)相遇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;//這里可以驗(yàn)證鏈表是不是環(huán)狀的，將size改為兩倍大小，看是否循環(huán)輸出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;