快慢指针
所谓的快慢指针的快慢是指指针向前移动的步长。比如在单链表中，快指针每次向前移动2个步长，慢指针则每次向前移动1个步长。
单链表环
单链表有环的定义是链表的尾节点指向了链表中间的某个结点。比如下图。（图片来自）
解题思路
判断单链表是否有环同样利用快慢指针的原理， 设置快慢指针 *fast 、 *slow 都指向单链表的头节点， 其中 *fast 的移动速度是 *slow 的2倍。如果是有环的链表的话，快指针始终都会追上慢指针。即在循环的过程中判断两指针是否会相等，如果相等，则是。
如果判断出单链表有环，如何找到环的入口，比如上图中，D就是环的入口。假设慢指针移动了S个结点，则快指针移动了2S个结点，如果环入口离头结点为x，环入口离相遇的那个结点为y，环的长度为r,单链表总长度为L，他们的关系推导如下：
从最后一个式子知道，L – x – y为相遇点到环入口的距离，也就是说一个指针从头结点出发，另一个指针从相遇点出发，，步长都为1的话，这两个指针一定会在环入口相遇。
代码实现是否有环int Is_ListLoop(LinkList L){LinkList fast, slow;if(L == NULL || L->next == NULL){exit(ERROR);}fast = slow = L;while(fast->next != NULL && fast->next->next != NULL){slow = slow->next;fast = fast->next->next;if(fast == slow){printf(“the List is Loop\n”);return TRUE;}}printf(“the List is no Loop\n”);return FALSE;}找到环入口int Find_Loop(LinkList L){LinkList fast, slow;if(L == NULL || L->next == NULL){exit(ERROR);}fast = slow = L;while(fast->next != NULL && fast->next->next != NULL){slow = slow->next;fast = fast->next->next;if(fast == slow){printf(“the List is Loop\n”);break;}}slow = L;while(fast != slow){slow = slow->next;fast = fast->next;}printf(“%d\n”,slow->data );return FALSE;}测试代码
测试代码中包括创建无环链表和有环链表，分别对应不同的打印链表函数。创建有环链表，第一数表示创建链表的长度，第二个表示链表尾结点指向哪个结点。
typedef struct Node {int data;struct Node *next;} Node, *LinkList;/*随机产生n个元素的带表头的单链表（头插法）*/void CreatList_Head(LinkList *L, int n) {int i;LinkList p;srand(time(0));(*L) = (LinkList)malloc(sizeof(Node));if (!(*L)) {exit(ERROR);}(*L)->next = NULL;for (i = 0; i < n; i++) {p = (LinkList)malloc(sizeof(Node));if (!p) {exit(ERROR);}p->data = rand() % 100 + 1;p->next = (*L)->next;(*L)->next = p;}}/*随机产生n个元素的带表头的单链表（尾插法）*/void CreatList_Tail(LinkList *L, int n) {LinkList p, r;int i;srand(time(0));(*L) = (LinkList)malloc(sizeof(Node));if (!(*L)) {exit(ERROR);}r = (*L);for (i = 0; i < n; i++) {p = (LinkList)malloc(sizeof(Node));if (!p) {exit(ERROR);}p->data = rand() % 100 + 1;r->next = p;r = p;}r->next = NULL;}void Print_List(LinkList L) {LinkList p;if (!L) {exit(ERROR);}p = L->next;while (p) {printf(“%d “, p->data);p = p->next;}printf(“\n”);}void Clear_List(LinkList *L){LinkList p,q;if((*L) == NULL)exit(ERROR);p = (*L)->next;while(p){q = p->next;free(p);p = q;}(*L)->next = NULL;}void Print_List_noHead(LinkList L) {LinkList p;if (!L) {exit(ERROR);}p = L;while (p) {printf(“%d “, p->data);p = p->next;}printf(“\n”);}int Creat_ListLoop(LinkList *L, int n, int loop_index) {LinkList p, r,q;int i;srand(time(0));(*L) = (LinkList)malloc(sizeof(Node));if (!(*L)) {exit(ERROR);}r = (*L);for (i = 0; i < n; i++) {p = (LinkList)malloc(sizeof(Node));if (!p) {exit(ERROR);}p->data = rand() % 100 + 1;r->next = p;r = p;if(i == (loop_index – 1))q = r;}r->next = q;}void Print_List_Loop(LinkList L, int n) {LinkList p;int i;if (!L) {exit(ERROR);}p = L->next;for(i = 0; i < n; i++){printf(“%d “, p->data);p = p->next;}printf(“\n”);}int Is_ListLoop(LinkList L){LinkList fast, slow;if(L == NULL || L->next == NULL){exit(ERROR);}fast = slow = L;while(fast->next != NULL && fast->next->next != NULL){slow = slow->next;fast = fast->next->next;if(fast == slow){printf(“the List is Loop\n”);return TRUE;}}printf(“the List is no Loop\n”);return FALSE;}int Find_Loop(LinkList L){LinkList fast, slow;if(L == NULL || L->next == NULL){exit(ERROR);}fast = slow = L;while(fast->next != NULL && fast->next->next != NULL){slow = slow->next;fast = fast->next->next;if(fast == slow){printf(“the List is Loop\n”);break;}}slow = L;while(fast != slow){slow = slow->next;fast = fast->next;}printf(“%d\n”,slow->data );return FALSE;}int main(int argc, char const *argv[]){LinkList L;CreatList_Head(&L, 11);Print_List(L);Is_ListLoop(L);Clear_List(&L);Creat_ListLoop(&L, 4, 2);Print_List_Loop(L,8);Is_ListLoop(L);Find_Loop(L);return 0;}
要做一个积极勇敢乐观的追梦人，永远不说消极的话，
