leetcode:141. 环形链表
程序员文章站
2022-04-04 08:31:08
...
-
题目描述
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
-
思路
假设环形链表如上图所示,有两个指针:快指针一次走两步,慢指针一次走一步。如果有环,它们必定会相遇。如果没有相遇,则证明没有环。 - c++实现
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
bool hasCycle(ListNode *head)
{
ListNode *fast=head;
ListNode *slow=head;
while(fast!=NULL && fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
break;
}
if(fast==NULL||fast->next==NULL)
return false;
return true;
}
int main()
{
ListNode *head=new ListNode(3);
head->next=new ListNode(2);
head->next->next=new ListNode(0);
head->next->next->next=new ListNode(-4);
head->next->next->next->next=head->next;
if(hasCycle(head))
cout<<"has cycle"<<endl;
else
cout<<"no cycle"<<endl;
return 0;
}