题目描述
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
样例
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
算法1
一次遍历
这里用一个有点耍赖皮的小技巧,用INT_MAX标记遍历过的节点,一次遍历就可以判断是否有环路存在。
时间复杂度
O(n)
C++ 代码
class Solution {
public:
bool hasCycle(ListNode *head) {
while(head!=NULL)
{
if(head->val==INT_MAX) return 1;
head->val=INT_MAX;
head=head->next;
}
return 0;
}
};
但是如果题目要求不能更改数据你这就不行了,比如142,hhhhhhh
👍