Phát Hiện Chu Trình Trong Danh SáchLinked List Cycle
Hiểu bài
Cho head của một danh sách liên kết (linked list).
Trả về true nếu danh sách có chu trình — tức tồn tại một node mà đi theo next mãi sẽ quay lại nó.
ts
// 3 → 2 → 0 → -4
// ↑_________| (-4.next trỏ về node 2) → true
// 1 → 2 → null → falseCó chu trình thì duyệt next sẽ chạy vô tận.
- Mẹo kinh điển: hai con trỏ chạy lệch tốc độ (nhanh & chậm).
- Nếu có vòng, con trỏ nhanh sẽ "đuổi kịp" con trỏ chậm bên trong vòng.
Cách cơ bản
O(n) time, O(n) spacets
function hasCycleSet(head: ListNode | null): boolean {
const seen = new Set<ListNode>()
for (let node = head; node; node = node.next) {
if (seen.has(node)) return true // gặp lại node đã thăm → có chu trình
seen.add(node)
}
return false // chạm null → có điểm cuối, không vòng
}Vì sao cách này chậm:
Cách này lưu mọi node đã thăm vào một Set để phát hiện lặp lại.
Đúng nhưng tốn O(n) bộ nhớ; kỹ thuật nhanh & chậm đạt cùng O(n) time mà chỉ O(1) bộ nhớ.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.