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