数据结构学习笔记：链表环

1.检测链表是否存在环。利用快慢指针实现，记录相遇位置。

// 判断单链表中是否存在环
bool IsListLoop(LinkList L, LinkList *pMeet = NULL)
{
	if ((NULL == L) || (NULL == L->next))
	{
		return false;
	}

	// 采用快慢指针，若快慢指针相等，则存在环
	LinkList pFast, pSlow;
	pSlow = L->next;
	pFast = L->next->next;

	while ((NULL != pFast) && (NULL != pFast->next))
	{
		if (pFast == pSlow)
		{
			*pMeet = pFast;
			return true;
		}

		pSlow = pSlow->next;
		pFast = pFast->next->next;
	}

	return false;
}

2. 检测链表环入口。

1）最开始想到的是暴力的方法，从头结点开始遍历。

// 检测单链表中环入口,暴力解法，复杂度O(n^2)
LinkList ListLoopEntranceDirect(LinkList L)
{
	// 暴力解法，从表头开始逐一往后遍历，每次循环一遍环
	// 若相遇，则为环的入口

	LinkList pMeet = NULL;
	if (!IsListLoop(L, &pMeet))
	{
		return NULL;
	}

	LinkList p = L;
	LinkList q = pMeet;
	while (p != q)
	{
		q = q->next;
		if (pMeet == q)
		{
			p = p->next;
		}
	}

	return q;
}

2）想想应该有优化的方法，尝试了头结点开始每次偏移两个指针长度。

// 检测单链表中环入口，暴力解法基础上进行，复杂度O(nlogn)
LinkList ListLoopEntranceOptimize(LinkList L)
{
	// 暴力解法基础上，每次移动两个，逐一遍历环
	// 保存当前指针和前一指针，相遇时得到环入口

	LinkList pMeet = NULL;
	if (!IsListLoop(L, &pMeet))
	{
		return NULL;
	}

	LinkList p = L;
	LinkList q = pMeet;
	while ((p != q) && (p->next != q))
	{
		q = q->next;
		if (pMeet == q)
		{
			p = p->next->next;
		}
	}

	return q;
}

3）查了一下网上的解决方法，果然还是有更好的方法，原理见https://blog.csdn.net/weixin_40807247/article/details/91447922，自己动手实现了一下，果然厉害

// 检测单链表中环入口，最优方法，复杂度O(n)
LinkList ListLoopEntranceBest(LinkList L)
{
	LinkList pMeet = NULL;
	if (!IsListLoop(L, &pMeet))
	{
		return NULL;
	}

	LinkList q = L;
	while (q != pMeet)
	{
		pMeet = pMeet->next;
		q = q->next;
	}

	return q;
}