题解 | #牛牛队列成环#
牛牛队列成环
https://www.nowcoder.com/practice/38467f349b3a4db595f58d43fe64fcc7
解题思路
总体而言是需要判断链表中是否有环,我们可以使用双指针的方法解决。
- 设置一个快指针,一个慢指针;
- 当快指针及其next值都不为空的时候,就开始遍历链表。如果快慢指针指向的节点值相等时,则说明是有环的,直接返回true。否则的话,慢指针走一步,快指针走两步。如果有环总会遇见的,没环就会到链表结尾,然后退出循环,返回false。
代码
代码一
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return bool布尔型
*/
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr)
{
return false;
}
ListNode* left = head;
ListNode* right = head->next;
while (left->val != right->val)
{
if(right == nullptr || right->next == nullptr)
{
return false;
}
left = left->next;
right = right->next->next;
}
return true;
}
};
代码二
将上述代码精简一下,如下所示:
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return bool布尔型
*/
bool hasCycle(ListNode* head) {
ListNode* left = head;
ListNode* right = head->next;
while (right != nullptr && right->next != nullptr)
{
if(left->val == right->val)
{
return true;
}
left = left->next;
right = right->next->next;
}
return false;
}
};
复杂度
- 时间复杂度:;
- 空间复杂度:。