题目描述
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
样例
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。
题意:
1、如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
2、根据题意,可知存在链表为空的情况,也存在只有一个节点的情况,需要特判。
算法1
第一种解法():
之前遍历到的节点,进行标记,如果再次遍历到,则说明该节点为环的入口节点。
设置一个标记数组,可以是vector、list、map(map查询的效率快一点,但存储的都是n个节点)等,记录已经出现过一次的节点(即之前已经遍历到的节点)。
遍历链表时,在标记数组中查询当前节点是否出现过,如果出现过,则为环的入口节点,直接返回。
如果没有出现过,则将当前的节点放入标记数组中,以便后续查询。
时间复杂度
时间复杂度:遍历每个节点时,都需要在标记数组中进行遍历查询(遍历查询为O(n)),因此时间复杂度为O(n^2)
空间复杂度
空间复杂度:申请一个标记数组,大小为链表大小,因此空间复杂度为O(n)
C++ 代码
bool hasCycle(ListNode *head) {
// 特判空链表或只有一个节点的链表
if(head==nullptr||head->next==nullptr) return false;
list<ListNode*> listNode;
while(head)
{
auto it=find(listNode.begin(),listNode.end(),head);
if(it!=listNode.end()) return true; // 如果在标记数组中查询到,则表示该节点遍历了两次,则为环的入口节点
else listNode.push_back(head); // 否则将该节点放入list中
head=head->next;
}
return false;
}
算法2
两个指针变量,一个慢指针(一次走一步),一个快指针(一次走两步),让这两个指针向后走,如果相遇了则表示有环,如果快指针走到链表尾还没有相遇(有环链表是不会结束的,即不会存在链表尾,会一直遍历),则表示无环
特殊注意快指针是否存在next,如果没有next,不能走到 指针->next->next,即不能走两步
!!!两个指针需要先走,再进行判断,不可以先判断后遍历,因为一开始赋值都为head,此时进行判断的话,肯定是相交,但和实际不符
时间复杂度
O(n)
空间复杂度
O(1)
C++ 代码
bool hasCycle(ListNode *head) {
// 特判空链表或只有一个节点的链表
if(head==nullptr||head->next==nullptr) return false;
// 快慢指针
ListNode* pFast=head;
ListNode* pSlow=head;
while(pFast&&pSlow)
{
// 慢指针走一步,快指针走两步
pSlow=pSlow->next;
if(pFast->next) pFast=pFast->next->next; // 如果pFast->next不为空,才可以走到pFast->next->next
else return false; // 如果pFast->next为空,则表示快指针走到表尾,则该链表不存在环,如果有环,则会一直遍历,不会停止
// 判断是否相交
if(pFast==pSlow) return true;
}
return false;
}