给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。
解法一: unordered_set容器
遍历链表,每次判断unordered_set容器中是否有存在head节点,如果存在则说明有环,否则就将此链表插入到unordered_set容器中继续遍历链表,直到遍历完链表,说明不存在环,返回false。
//使用unordered_set容器
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set< ListNode* > s; //使用无序set容器
while(head!=NULL)
{
if(s.count(head)) //如果s中有head那么说明链表有环
{
return true;
}
else //否则将此节点插入到unordered_set中 继续遍历链表
{
s.insert(head);
}
head=head->next;
}
return false;//直到遍历完链表 返回false
}
};
解法二:快慢指针
乌龟和兔子都在链表上移动,乌龟走的慢,如果有环的话,兔子先进入环,而后乌龟一直在后面,过一段时间后,走的快的兔子就必定会再次追上乌龟。否则说明兔子到终点,不存在环。
首先,如果传入的head为空,则说明不存在环,返回false。
定义快慢指针,快指针一次走2步,慢指针一次走1步,如果相遇则说明存在环,否则快指针到达终点,不存在环。
//快慢指针
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL) //如果链表为空,则肯定不为环形链表 返回为false
{
return false;
}
ListNode* fast = head;
ListNode* slow = head;
while( fast!=NULL && fast->next!=NULL )
{
fast=fast->next->next; //快指针走2步
slow=slow->next; //慢指针走1步
if(fast==slow)
{
return true; //相遇则说明有环
}
}
return false; //此时while循环退出则说明快指针走到尾 ,不存在环形链表
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)