Trong quá trình phát triển ứng dụng phía client hoặc server, cấu trúc dữ liệu Linked List đôi khi được sử dụng để xây dựng các bộ nhớ đệm đơn giản hoặc lịch sử thao tác. Làm thế nào để thực hiện việc kiểm tra xem một Linked List đơn có chứa chu kỳ hay vòng lặp (Cycle Detection) với độ phức tạp bộ nhớ O(1)?

Question

Accepted Answer

Để phát hiện chu kỳ trong một Linked List đơn với độ phức tạp không gian O(1), chúng ta sử dụng thuật toán Floyd Cycle-Finding, thường được gọi là thuật toán Con thỏ và Con rùa (Tortoise and Hare Algorithm).
Cơ chế hoạt động
Chúng ta sử dụng hai con trỏ khởi tạo tại điểm head của danh sách:

Con trỏ rùa (Slow Pointer): Di chuyển từng bước một (1 node mỗi lần).
Con trỏ thỏ (Fast Pointer): Di chuyển hai bước một (2 node mỗi lần).

Nếu danh sách không có chu kỳ, con trỏ thỏ sẽ đi đến phần tử null kết thúc danh sách. Ngược lại, nếu danh sách có chu kỳ, do con trỏ thỏ di chuyển nhanh hơn, nó sẽ đuổi kịp con trỏ rùa ở một node nào đó bên trong vòng lặp.
Ví dụ cài đặt (JavaScript)
function hasCycle(head) {
    if (!head || !head.next) return false;

let slow = head;
    let fast = head;

while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

if (slow === fast) {
            return true; // Phát hiện có vòng lặp
        }
    }

return false; // Không có vòng lặp
}
Lưu ý thực chiến
Thuật toán này có độ phức tạp thời gian là O(N) trong trường hợp xấu nhất và độ phức tạp bộ nhớ là O(1) vì chỉ sử dụng hai biến con trỏ phụ trợ. Đây là câu hỏi kinh điển ở cấp độ Junior nhằm đánh giá khả năng tối ưu hóa bộ nhớ và tư duy logic thuật toán.

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi linked lists liên quan cùng chủ đề