Làm thế nào để xác định xem một danh sách liên kết có chứa một vòng lặp?

Question

Bản sao có thể xảy ra:
find whether a loop in a linked list without two pointers
How to determine if a linked list has a cycle using only two memory locations.
Best algorithm to test if a linked list has a cycle

Trong một sự chuẩn bị cho một cuộc phỏng vấn việc làm, tôi gặp phải những câu dưới đây:

Làm thế nào bạn có thể xác định liệu một danh sách liên kết (thuộc bất kỳ loại nào) chứa một vòng lặp, sử dụng additio Nal không gian phức tạp của O (1)? Bạn không thể giả định rằng vòng lặp bắt đầu tại nút đầu tiên (và tất nhiên, vòng lặp không phải chứa tất cả các nút).

Tôi không thể tìm thấy câu trả lời, mặc dù tôi có cảm giác nó khá đơn giản ...

Answer 1

Dễ dàng. Duy trì hai con trỏ vào danh sách. Tại mỗi bước, trước một con trỏ bằng một liên kết duy nhất và chuyển tiếp một con trỏ khác bằng hai liên kết. Kiểm tra xem liệu chúng có trỏ đến cùng một phần tử hay không. Nếu vậy, bạn có một vòng lặp. Nếu không, hãy lặp lại cho đến khi bạn tìm thấy một vòng lặp hoặc bạn đến cuối danh sách.

Answer 2

Có lẽ kỹ thuật tương tự như kiểm tra xem biểu đồ có phải là cây không (cây không có chu kỳ), xem this this question. Nó đề nghị hoặc là một loại topo hoặc một tìm kiếm đầu tiên chiều sâu.

Answer 3

Tôi gặp sự cố chính xác này trong mã trực tiếp thực tế vào tuần trước.

Tất cả những gì tôi đã làm được giữ một con trỏ (liên kết) cho phần tử đầu tiên. Sau đó, khi tôi lặp lại qua danh sách, nếu tôi lại có con trỏ đó, tôi biết có một vòng lặp.