判断单链表是否有环

单链表是最常见的数据结构，带环的单链表不是很常见，但是在许多面试中出现的概率较高，其中不乏一些经典的问题，怎样判断单链表中是否有环。

单链表带环指的是如下这张图所示情况：

其实思想还是挺简单的：

我们需要两个指针，初始时都指向链表的头，之后指针同时移动，其中一个指针一次移动一步，另一个指针一步移动两步，如果两个指针有相等的可能，则链表就是有环的，否则，出现一个指针指向了 NULL ，那么这个链表就是肯定不带环的。

下面给出具体的实现：

#include <stdio.h>#include <malloc.h>typedef int DataType;typedef struct node{DataType data;struct node *next;}LinkedNode, *LinkList;LinkList create_list(int *a, int pos, int len);int is_exist_loop(LinkList list);int main(int argc, char **argv){int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};LinkList list_head = NULL;int result = -1;list_head = create_list(array, 10, sizeof(array) / sizeof(int));result = is_exist_loop(list_head);if(result == 0){printf("This list has loop\n");}else if(result == -1){printf("This list don't has loop\n");}else{printf("error\n");}}/*根据条件建立单链表*//** a 链表初始化数组* pos 环的位置，若为 0 或者大于 数组长度则不带环* len 数组的长度*/LinkList create_list(int *a, int pos, int len){LinkedNode *temp = NULL; int i = 0;LinkedNode *record = NULL;LinkedNode *list_head = NULL;LinkedNode *p = NULL;if(a == NULL){return NULL;}if(pos == 0 || pos > len){record = NULL;}list_head = (LinkedNode*)malloc(sizeof(LinkedNode));list_head->data = a[0];list_head->next = NULL;temp = list_head;for(i = 1; i < len; i++){while(temp->next != NULL){temp = temp->next;}p = (LinkedNode *)malloc(sizeof(LinkedNode));p->data = a[i];p->next = NULL;temp->next = p;if((i + 1) == pos){record = p;}}temp = list_head;while(temp->next != NULL){temp = temp->next;}temp->next = record;return list_head;}/*判断单链表是否带环*/int is_exist_loop(LinkList list){int result = -1;LinkedNode *one_step = NULL;LinkedNode *two_step = NULL;one_step = list;two_step = list;while(two_step != NULL && two_step->next != NULL){one_step = one_step->next;two_step = two_step->next->next;if(one_step == two_step){result = 0;break;}}return result;}