传送门
快慢指针
typescript
// JS
function hasCycle(head) {
// 初始化慢指针和快指针
let slow = head;
let fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针每次前进一步
fast = fast.next.next; // 快指针每次前进两步
if (slow == fast) { // 如果它们相遇,则说明存在环
return true;
}
}
// 如果快指针 reaches 到链表末端,说明链表无环
return false;
}
哈希
typescript
var hasCycle = function (head) {
if (head === null) return false;
let set = new Set();
while (head) {
if (set.has(head)) return true;
set.add(head);
head = head.next;
}
return false;
};