LeetCode 热题 100_环形链表（25_141_简单_C++）(哈希表；快慢指针)

题目描述：

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

输入输出样例：

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围是 [0, 10⁴]
-10⁵ <= Node.val <= 10⁵
pos 为 -1 或者链表中的一个 有效索引 。

题解：

解题思路：

思路一（哈希表）：

1、使用一个哈希集合来存储遍历到的结点的地址。如果遍历到的结点不存在哈希集合中，则将该节点添加到哈希集合中。如果遍历到的结点已经存在哈希集合中则存在环，如果遍历整个链表结束则无环。

2、解题步骤
① 创建哈希集合用于进行环的判断。
② 遍历链表中的结点，如果遍历到的结点不存在哈希集合中，则将该节点添加到哈希集合中。如果遍历到的结点已经存在哈希集合中则存在环。
③ 遍历整个链表结束则无环。

3、复杂度分析：
① 时间复杂度：O(N)，其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次（环可能在中间部分）。
② 空间复杂度：O(N)，其中 N 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

思路二（快慢指针）：

1、使用快慢指针，快指针每次移动2步，慢指针每次移动1步。如果没有环，fast会先到达末尾nullptr。如果存在环的话，快指针与慢指针会在环中每次缩进一个单位的距离，最终快指针会追上慢指针，达到fast=slow的条件。

2、解题步骤
① 首先判断链表是否为空，第一个结点的next是否为空。
② 将slow指向首节点，fast指向首节点的next结点（防止一开始slow=fast的情况，且注意一个结点也可成环）。
③ 遍历单链表，slow指针每次移动一步，fast指针每次移动两步。
④ 如果fast到达链表的末尾则无环，如果最后fast==slow则存在环。

3、复杂度分析
① 时间复杂度：O(N)，其中 N 是链表中的节点数。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，为O(N/2)。
当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。当慢指针移动到进入环的结点时，此时快指针已经在环上，快慢指针的最大距离为环的长度减一，所以。所以为O(N)。

② 空间复杂度：O(1)。我们只使用了两个指针的额外空间。

代码实现

代码实现（思路一（哈希表））：

bool hasCycle1(ListNode *head) {
	//mp用于存放没遍历过的结点地址
	unordered_set<ListNode*> mp;
	//如果遍历到的结点不存在哈希集合中，则将该节点添加到哈希集合中。如果遍历到的结点已经存在哈希集合中则存在环。
	while(head!=nullptr) {
		if(mp.count(head)){
			return true;
		}
		mp.insert(head);
		head=head->next;
	}
	return false;
}

代码实现（思路二（快慢指针））：

bool hasCycle2(ListNode *head) {
	//先排除特殊情况方便快慢指针的赋值 
	if(head==nullptr||head->next==nullptr){
		return false;
	}
	//注意初始时fast是slow后的一个结点（避免一开始相同的情况） 
	ListNode *fast=head->next,*slow=head;
	//当slow==fast时存在环，如果fast到达末尾则不存在环 
	while(slow!=fast){
		if(fast==nullptr||fast->next==nullptr){
			return false;
		}
		fast=fast->next->next;
		slow=slow->next; 
	} 
	return true;
}

以思路二为例完成代码调试

#include<iostream>
#include<vector>
using namespace std;

struct ListNode{
	int val;
	ListNode *next;
	ListNode(int x):val(x),next(nullptr){}
};

//尾插法创建单链表 
ListNode* createList(const vector<int> &a){
	ListNode *head=nullptr,*tail=nullptr;
	for(const auto &val:a){
		ListNode *newNode=new ListNode(val);
		if(head==nullptr){
			head=newNode;
			tail=newNode;
		}else{
			tail->next=newNode;
			tail=newNode;
		}
	} 
	return head;
}

//将单链表改成环状链表（注意这里仅构造末尾存在环的情况）
ListNode* createCircularList(ListNode *head,int pos){
	if(pos==-1){
		return head;
	} 
	ListNode *posNode=head;
	//找到环形的入口结点 
	while(pos){
		posNode=posNode->next;
		--pos;
	}
	//从入口结点到尾结点 
	ListNode *tail=posNode;
	while(tail->next!=nullptr){
		tail=tail->next;
	}
	//将尾节点的next指针指向入口节点形成环 
	tail->next=posNode;
	return head;
} 

//判断是否构成环形链表
bool hasCycle2(ListNode *head) {
	//先排除特殊情况方便快慢指针的赋值 
	if(head==nullptr||head->next==nullptr){
		return false;
	}
	//注意初始时fast是slow后的一个结点（避免一开始相同的情况） 
	ListNode *fast=head->next,*slow=head;
	//当slow==fast时存在环，如果fast到达末尾则不存在环 
	while(slow!=fast){
		if(fast==nullptr||fast->next==nullptr){
			return false;
		}
		fast=fast->next->next;
		slow=slow->next; 
	} 
	return true;
}

int main(){
	vector<int> a={1,2};
	int pos=0;
	//创建单链表 
	ListNode *head=createList(a);
	//将单链表形成环 
	ListNode *cir_head=createCircularList(head,pos);
	
	//判断是否存在环 
	if(hasCycle2(cir_head)){
		cout<<"It's a circular linked list";
		
	}else{
		cout<<"It's not a circular linked list";
	}
	
	return 0;
} 

LeetCode 热题 100_环形链表（25_141)原题链接

unordered_map和unordered_set对比及用法请点击此链接

ListNode(int x):val(x),next(nullptr){}解读请点击此链接

欢迎大家和我沟通交流(✿◠‿◠)