例题-链表中环的入口结点

描述

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

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

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

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

答案及解析

此题与NC4-判断链表中是否有环异曲同工

1. hash法(better!)

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

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

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

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

ListNode* EntryNodeOfLoop(ListNode* pHead) {
{
	if ( !pHead )
		return nullptr;
	ListNode* fast = pHead;
	ListNode* slow = pHead;
	while ( fast && fast->next )
	{
		fast = fast->next->next;
		slow = slow->next;
		if ( fast == slow )
			return slow;
	}
	return nullptr;
}