[数据结构与算法]【快慢指针_判断链表中是否存在环形_(C语言实现)】

快慢指针

指的是有两个指针，每次前进的距离不同
快慢指针的起点都一样：
前进快的就是快指针 前进慢的就是慢指针
快指针每次前进2格 慢指针每次前进一格

bool QuikSlow(struct Node* head)
{
	//参数合法性检测
	if (NULL == head)
		return false;
	struct Node* quik = head->pNext;
	struct Node* slow= head->pNext;

	while (quik != NULL && quik->pNext != NULL)
	{
		slow = slow->pNext;
		quik = quik->pNext->pNext;
		if (slow == quik)
			return true;
	}
	return false;
}

（一）检测单链表是否有环：

    定义两个指针，一个快一个慢，两个指针刚开始时都指向链表的头节点，之后快指针每次前进两步，慢指针每次前进一步，如果他们相遇了（fast= low），说明快指针已经转了一圈回来了，也就说明链表有环。

（二）返回环的入口：

     同样定义两个指针，一个指向头节点，另一个指向相遇点，两个指针同时向后走，他们的第一次相遇点就是环的入口。

分析：

    就类似于在操场的跑道上跑步，两个人，快的人的速度是慢的人的两倍，跑的快的人，在第二圈会再次与跑的慢的人相遇。

简单实例实现：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stdbool.h>

struct Node
{
	int a;
	struct Node* pPre;
	struct Node* pNext;
};

void Add(struct Node* head, int iData)
{
	//参数合法性检测
	if (NULL == head)
		return;
	//申请节点
	struct Node* pTemp = (struct Node*)malloc(sizeof(struct Node));
	//节点赋值
	if (pTemp == NULL)
		return;
	pTemp->a = iData;
	pTemp->pNext = NULL;
	pTemp->pPre = NULL;
	//链接
	//先连 将新节点连在指定位置
	pTemp->pPre = head->pPre;
	pTemp->pNext = head;
	//后断
	head->pPre->pNext = pTemp;
	head->pPre = pTemp;
}
void Free(struct Node* head)
{
	//参数合法性检测
	if (NULL == head)
		return;
	//申请节点
	struct Node* pTemp = head;
	while (pTemp != head)
	{
		pTemp = pTemp->pNext;
		free(pTemp->pPre);
	}
	head->pPre = head;
	head->pNext = head;
}

bool QuikSlow(struct Node* head)
{
	//参数合法性检测
	if (NULL == head)
		return false;
	struct Node* quik = head->pNext;
	struct Node* slow= head->pNext;

	while (quik != NULL && quik->pNext != NULL)
	{
		slow = slow->pNext;
		quik = quik->pNext->pNext;
		if (slow == quik)
			return true;
	}
	return false;
}
int main()
{
	struct Node head;
	head.a = 0;
	head.pPre = &head;
	head.pNext = &head;
	Add(&head, 1);
	Add(&head, 2);
	Add(&head, 3);
	Add(&head, 4);
	Add(&head, 5);
	Add(&head, 6);

	//变成不循环的
	struct Node* pEnd = head.pPre;
	pEnd->pNext = NULL;
	head.pPre = NULL;

	//变成环
	pEnd->pNext = head.pNext->pNext->pNext;

	bool res = QuikSlow(&head);

	Free(&head);
	return 0;
}