题目地址：力扣
这道题目描述有问题，我读了好几遍都没看懂，正确的题目描述如下：
要求：给你一个链表的头节点指针head ，判断链表中是否有环。如果链表中存在环?，则返回 true 。 否则，返回 false 。
备注：测试用例中的pos是表示链表尾的next指向的节点；若链表无环，则pos=-1；若链表有环，则pos的值为链表中的位置下标（从0开始编号）。其中题目中每个节点的数字是迷惑作用，不同节点数字可以一样。
解法1：暴力求解
思路：用一个set来把碰到过的指针都存下来，如果在遍历的过程中发现set中有这个指针，那么说明有环，返回true。如果遍历到底了，都没有则返回false。
class Solution {
public:
bool hasCycle(ListNode *head) {
set<ListNode *> ptr_set; // 用来存储指针的set
if (head != nullptr) // 边界条件，初始链表为空
{
while (head->next != nullptr) // 遍历
{
if (ptr_set.find(head->next) == ptr_set.end())
{
ptr_set.insert(head->next);
head = head->next;
}
else
return true;
}
}
return false;
}
};
解法2：快慢指针
思路：使用一块一慢两个指针，若链表有环，慢的指针迟早都会和快的指针相遇
这里快指针一次走2步，走3步，甚至走更多步都可以，慢指针一定要比快指针的步子小。
下面的代码是快指针一次走2步，慢指针一次走1步
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fastptr = head; // 快指针一次走两步
ListNode *slowptr = head; // 满指针一次走一步
while (fastptr != nullptr && fastptr->next != nullptr) //无环的边界条件
{
fastptr = fastptr->next->next;
// 快指针走完判断一次
if (slowptr == fastptr)
return true;
slowptr = slowptr->next;
// 慢指针走完判断一次
if (slowptr == fastptr)
return true;
}
return false;
}
};
还可以写成快指针一次3步，慢指针一次2步
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fastptr = head;
ListNode *slowptr = head;
while (fastptr != nullptr && fastptr->next != nullptr && fastptr->next->next != nullptr)
{
fastptr = fastptr->next->next->next;
if (slowptr == fastptr)
return true;
slowptr = slowptr->next->next;
if (slowptr == fastptr)
return true;
}
return false;
}
};
虽然复杂度都是O(n)，但是如果圈子特别大的话，步数大就能使得指针提早进入圈子
Accepted
- 21/21 cases passed (8 ms)
- Your runtime beats 93.03 % of cpp submissions
- Your memory usage beats 96.97 % of cpp submissions (7.7 MB)
|