环形链表
题目描述
思路
方法一：哈希表
遍历整个链表，利用一个哈希表来储存遍历过的节点。在每次遍历时，判断当前节点是否已经在哈希表中，如果在，说明有环，返回true，否则将当前节点加入哈希表中。如果head指向空，即遍历结束都没有找到重复的节点，说明没有环，返回false。
这个方法的时间复杂度是$O(N)$，空间复杂度也是$O(N)$。
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> hashtable;
while(head != nullptr) {
if (hashtable.count(head)) return true;
hashtable.insert(head);
head = head->next;
}
return false;
}
};
方法二：快慢指针
由于无论如何都需要遍历整个链表，因此时间复杂度都是$O(N)$，但是空间复杂度可以降到$O(1)$。这里可以使用快慢指针的想法实现。
快慢指针的想法基于“Floyd判圈算法（龟兔赛跑算法）”。假想两个速度不同的跑步者在环形赛道上赛跑，如果一开始他们都位于环形赛道上，那么跑得快的人一定会从后面追上跑得慢的人，这是因为在某个时刻后，慢跑者在环形赛道上的某个位置，而快跑者在环形赛道上的某个位置，且这两个位置之间的距离是有限的，因此快跑者一定会追上慢跑者。
根据此想法，设置一个快指针fast和一个慢指针slow。初始状态时，fast位于head位置，而slow位于head->next位置。不断循环，当fast追上slow，即二者重合时，则说明链表有环，返回true；如果fast到达链表尾部，则说明链表无环，返回false。
class Solution {
public:
bool hasCycle(ListNode *head) {
// 必须先判断一下head是不是空指针，否则会报错
if (head == nullptr || head->next == nullptr) return false;
ListNode* fast = head->next;
ListNode* slow = head;
while(slow != fast) {
if (fast == nullptr || fast->next == nullptr) return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
文档信息
- 本文作者：焦逸凡
- 本文链接：https://ailovejinx.github.io/wiki/leetcode141/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）