Problem: 141. 环形链表
解析
hash表
hash表不用多说。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
bool hasCycle(ListNode *head) {
std::unordered_map<ListNode *, bool> hashTable;
ListNode *node = head;
while (node != nullptr) {
if (hashTable.find(node) != hashTable.end()) {
return true;
}
hashTable[node] = true;
node = node->next;
}
return false;
}
};
|
快慢指针
重点说下快慢指针，当双指针都进入环中，循环下来fast必定和slow碰面，这保证了正确性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr) {
return false;
}
ListNode *fast, *slow;
fast = head, slow = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
|
