Linked List Cycle: vì sao rùa nhất định bắt kịp thỏ

Bài toán cho bạn head của một linked list và hỏi một điều: liệu việc liên tục theo con trỏ next có bao giờ dẫn về một node đã đi qua không? Cycle có thể đóng lại ngay tại node đầu tiên, ở đâu đó giữa chừng, hoặc không tồn tại. Bạn không thể biết độ dài danh sách từ bên ngoài — không có trường length nào — vì vậy bạn phải tự khám phá bằng cách đi qua.

Danh sách [3, 2, 0, -4] với back-edge từ -4 về node 2 là Example 1. Back-edge đó vô hình từ bên ngoài — bạn chỉ phát hiện ra khi nhận thấy mình đã đến một node đã thăm rồi.

Đề bài

Cho head của một linked list, xác định xem danh sách có chứa cycle không — tức là liệu việc liên tục theo con trỏ next từ bất kỳ node nào có bao giờ dẫn trở lại một node đã đi qua. Full statement: LeetCode 141.

Ràng buộc:
- Số lượng node trong danh sách nằm trong khoảng [0, 10^4].
- -10^5 <= Node.val <= 10^5
- pos là -1 hoặc một index hợp lệ trong linked list.

Constraints nói gì trước khi bạn viết bất cứ thứ gì

Số lượng node nằm trong [0, 10^4]. Đủ nhỏ để O(n) về time hoàn toàn ổn, nhưng follow-up làm câu hỏi thiết kế trở nên rõ ràng: bạn có thể làm với O(1) space không?

Dải giá trị [-10^5, 10^5] không liên quan đến thuật toán — bạn đang so sánh node identity (địa chỉ bộ nhớ), không phải node value. Hai node có cùng .val ở các vị trí khác nhau là hai object khác nhau; một node mà next trỏ lại chính nó sẽ xuất hiện cùng một địa chỉ hai lần, không phải cùng giá trị hai lần.

pos được ghi trong đề là vị trí zero-indexed mà đuôi danh sách kết nối đến, nhưng nó không được truyền vào hàm của bạn. Hàm chỉ thấy head. Điều này có nghĩa là bạn không thể dựa vào bất kỳ metadata nào về cycle — bạn phải suy ra sự tồn tại của nó thuần túy từ hành vi duyệt.

Danh sách rỗng (n = 0) nằm trong phạm vi hợp lệ. head sẽ là None/null. Đây không phải edge case cần xử lý đặc biệt; nó tự nhiên rơi vào điều kiện dừng của bất kỳ traversal nào bạn dùng.

Approach 1: hash set membership

Cách đọc đơn giản nhất của bài toán: duyệt qua danh sách, giữ một set chứa mọi node đã thăm, và trả về true ngay khi gặp node đã có trong set.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        visited = set()
        current = head
        while current is not None:
            if current in visited:
                return True
            visited.add(current)
            current = current.next
        return False

public class Solution {
    public bool HasCycle(ListNode head) {
        var visited = new HashSet<ListNode>();
        ListNode current = head;
        while (current != null) {
            if (visited.Contains(current)) return true;
            visited.Add(current);
            current = current.next;
        }
        return false;
    }
}

Set lưu node reference, không phải value. Trong Python là object identity (id(current)); trong C#, HashSet dùng reference equality mặc định cho kiểu class. Hai node có cùng .val vẫn là hai object riêng biệt và sẽ không collide trong set.

Trace tay: [3, 2, 0, -4] với cycle tại index 1

Gọi địa chỉ node là A(3), B(2), C(0), D(-4), với D.next = B.

visited = {}
current = A  -> A chưa trong visited -> thêm A -> current = B
visited = {A}
current = B  -> B chưa trong visited -> thêm B -> current = C
visited = {A, B}
current = C  -> C chưa trong visited -> thêm C -> current = D
visited = {A, B, C}
current = D  -> D chưa trong visited -> thêm D -> current = B
visited = {A, B, C, D}
current = B  -> B ĐÃ trong visited -> return True

Bốn bước để phát hiện cycle. Trong danh sách không có cycle, current cuối cùng trở thành None và vòng lặp kết thúc.

Complexity

Time: O(n). Mỗi node được thăm nhiều nhất một lần trước khi match xảy ra hoặc ta đi hết danh sách. Lookup và insertion vào set là O(1) amortized.

Space: O(n). Trong trường hợp xấu nhất (không có cycle, hoặc cycle đóng lại ở bước cuối cùng), ta lưu mọi node vào set. Đây là cái giá của approach này, và follow-up đang chỉ thẳng vào đó.

Approach 2: Floyd's cycle detection — two pointers với tốc độ khác nhau

Floyd's algorithm (thuật toán "rùa và thỏ") không dùng thêm bộ nhớ. Hai pointer bắt đầu từ head. slow tiến một bước mỗi lần lặp; fast tiến hai bước. Nếu có cycle, fast sẽ cuối cùng lap slow và chúng gặp nhau trong cycle. Nếu không có cycle, fast rơi khỏi danh sách trước.

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

public class Solution {
    public bool HasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

Điều kiện vòng lặp kiểm tra cả fast lẫn fast.next trước khi di chuyển — bạn cần cả hai không null vì fast.next.next dereference hai cấp. Chỉ kiểm tra fast sẽ gây null-pointer exception ở lần dereference thứ hai trong danh sách có độ dài chẵn.

Tại sao chúng nhất định gặp nhau?

Giả sử danh sách có đoạn tail dài F trước khi cycle bắt đầu, và cycle có độ dài C. Khi slow vào cycle, fast đã ở đâu đó bên trong (nó vào trước C/2 bước và đang lapping). Định nghĩa gap là khoảng cách fast đang đi trước slow bên trong cycle. Mỗi bước, fast tiến hai vị trí và slow tiến một, nên gap giảm đi một mỗi lần lặp (modulo C). Từ một gap dương ban đầu, gap về 0 — chúng gặp nhau — trong nhiều nhất C bước. Toàn bộ quá trình kết thúc trong O(F + C) = O(n) time.

Trace tay: [3, 2, 0, -4] với cycle tại index 1

Cùng node: A(3), B(2), C(0), D(-4), D.next = B.

slow = A, fast = A

Bước 1: slow = B, fast = C   (fast nhảy 2 bước đến C=0)
Bước 2: slow = C, fast = B   (fast: C.next=D, D.next=B -> về B)
Bước 3: slow = D, fast = D   (fast: B.next=C, C.next=D -> D; slow: C.next=D -> D)
slow == fast -> return True

Ba bước. Điểm gặp nhau là tại -4, node D. Đó không nhất thiết là điểm vào cycle — để tìm điểm vào bạn cần bài mở rộng LeetCode 142.

Complexity

Time: O(n). Phân tích ở trên giới hạn nó tại O(F + C), và F + C <= n.

Space: O(1). Hai biến pointer. Không có gì khác.

Các edge case quan trọng ở bài này

Danh sách rỗng (head = None/null): Điều kiện while fast and fast.next sai ngay lập tức. Trả về false. Không cần guard đặc biệt.

Một node, không có self-loop ([1]): fast.next là null. Vòng lặp không chạy. Trả về false.

Một node với self-loop: fast.next là chính node đó (không phải null), nên vòng lặp chạy. Ở bước 1, slow = node, fast = node. Chúng gặp nhau ngay. Trả về true. Đây là lý do bạn kiểm tra slow == fast bên trong vòng lặp thay vì khởi tạo chúng ở vị trí khác nhau.

Hai node với cycle ([1, 2] trong đó 2.next = 1): Bước 1 di chuyển slow đến node 2 và fast (hai bước) về lại node 1, sau đó bước 2 đặt slow tại 1 và fast tại 1. Gặp nhau. Trả về true.

Danh sách dài, không có cycle: fast đến đuôi trong n/2 lần lặp. fast hoặc fast.next trở thành null, vòng lặp kết thúc, trả về false. Constraint n <= 10^4 đảm bảo điều này nhanh.

Cycle đóng lại tại node đầu tiên: F = 0. fast vào cycle ngay lập tức. Lý luận về gap vẫn đúng; chúng gặp nhau trong nhiều nhất C bước.

Bảng so sánh

Time complexity bằng nhau. Sự khác biệt là space. Hash set cấp phát bộ nhớ tỷ lệ với độ dài danh sách; Floyd's chỉ dùng hai biến local bất kể danh sách lớn đến đâu.

Cái tôi sẽ ship trong thực tế

Floyd's, không do dự. Đây là câu trả lời chuẩn cho follow-up, không tốn thêm bộ nhớ, và logic chỉ vài dòng. Hash set dễ giải thích hơn cho người chưa biết bài, nhưng khi bạn đã hiểu tại sao fast pointer nhất định đuổi kịp slow pointer, giải pháp two-pointer thực ra elegant hơn — bạn đang dùng chính cấu trúc tuần hoàn của bài toán để tự phát hiện nó.

Hash set có một lợi thế trong phỏng vấn: nếu bạn quên Floyd's trong lúc căng thẳng, approach set sẽ pass mọi test case và chứng minh bạn hiểu bài. Ship đúng trước, optimize khi được yêu cầu.

Pattern cốt lõi ở đây là fast-slow pointers — công cụ tiêu chuẩn cho bất kỳ câu hỏi nào yêu cầu phát hiện hoặc khai thác tính tuần hoàn trong một sequence mà không lưu trữ sequence đó. Ý tưởng rằng pointer đi nhanh gấp đôi nhất định sẽ lap pointer đi chậm hơn trong một cycle hữu hạn khái quát hóa vượt ra ngoài linked list — LeetCode 287 dùng nó trên array, LeetCode 202 dùng nó trên chuỗi số.

Vị trí trong series linked-list

Đây là bài thứ tư trong series, sau Reverse Linked List (206), Merge Two Sorted Lists (21), và Reorder List (143). Ba bài kia đều về thao tác pointer trong acyclic list: đảo chiều, merge hai chuỗi, nối lại các nửa. Linked List Cycle đưa vào câu hỏi detection — có gì đó sai với cấu trúc danh sách, và bạn cần tìm xem nó có bị hỏng không.

Linked List Cycle II (142) mở rộng trực tiếp: biết rằng cycle tồn tại, tìm node nơi cycle bắt đầu. Floyd's algorithm cho bạn điểm gặp nhau; một phase thứ hai (reset một pointer về head, tiến cả hai với tốc độ 1) cho bạn điểm vào. Toán học rất đẹp và đáng tự tính.

Middle of the Linked List (876) dùng cùng cơ chế fast-slow pointer: khi fast đến cuối, slow ở điểm giữa. Bài toán khác nhau, cùng intuition cấu trúc.

Find the Duplicate Number (287) đặt lại cycle detection hoàn toàn. Một array gồm n+1 số nguyên trong [1, n] có thể được mô hình hóa như linked list trong đó index i trỏ đến giá trị arr[i]. Nếu có số trùng lặp, giá trị đó được thăm hai lần — nghĩa là có cycle. Floyd's algorithm tìm số trùng lặp với O(1) space.

Happy Number (202) hỏi liệu việc liên tục thay một số bằng tổng bình phương các chữ số của nó có cuối cùng đến 1 không. Nếu quá trình đó cycle, nó không bao giờ đến 1. Áp dụng Floyd's trên sequence của các số thay vì node trong list. Cùng công cụ, bề mặt hoàn toàn khác.