例题-判断链表中是否有环

描述

来源：牛客-名企高频面试题高频TOP200

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 0 <= n <= 10000，链表中任意节点的值满足 |val| <= 100000

要求：空间复杂度 O(1)，时间复杂度 O(n)

答案及解析

1. hash法(better!)

使用哈希容器存储出现过的节点，重复出现时，即有环。

bool hasCycle(ListNode* head)
{
	unordered_set<ListNode*> set;
	while ( head )
	{
		auto res = set.emplace(head);
		/*
		emplace的返回值为pair<typename,bool>
		其中second的值插入成功为true，失败为false，由此即可判断，
		也可使用c++20新增的contains(牛客不支持好像)
		*/
		if ( res.second == false )
			return true;
		head = head->next;
	}
	return false;
}

2. 快慢指针(追及问题)

如上图所示为模拟的一个链表环。

1. 找环中相汇点。分别用fast，slow指向链表头部，slow每次走一步，fast每次走二步，直到fast==slow找到在环中的相汇点。
2. 找环的入口。接上步，当fast==slow时，fast所经过节点数为2x,slow所经过节点数为x,设环中有n个节点，fast比slow多走r圈有2x=rn+x; x=rn;（r为圈数，n为一圈的结点数）
3. 可以看出slow实际走了多个环的步数，再让fast指向链表头部，slow位置不变
4. 假设链表开头到环接口的距离是y，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = rn，即此时slow指向环的入口

通过定义快慢指针分别每次走一步与两步，当快指针追上慢指针时即可证明有环。(需要注意fast指针越界问题)

bool hasCycle(ListNode* head)
{
	if ( !head )
		return false;
	ListNode* fast = head;
	ListNode* slow = head;
	while ( fast && fast->next )
	{
		fast = fast->next->next;
		slow = slow->next;
		if ( fast == slow )
			return true;
	}
	return false;
}