---

Học cách tìm điểm bắt đầu của chu trình trong danh sách liên kết đơn với độ phức tạp O(N) thời gian và O(1) không gian bằng thuật toán Rùa và Thỏ.

Tìm điểm bắt đầu của chu trình: Giải mã toán học đằng sau thuật toán Rùa và Thỏ (LinkedList Cycle II)

Trong Bài trước, chúng ta đã tìm hiểu cách phát hiện xem một danh sách liên kết đơn (Linked List) có chu trình hay không bằng thuật toán Rùa và Thỏ (Floyd's Cycle-Finding Algorithm). Tuy nhiên, một câu hỏi hóc búa hơn thường xuất hiện trong các buổi phỏng vấn của các công ty công nghệ lớn: "Làm thế nào để tìm chính xác nút (node) bắt đầu của chu trình đó mà không tốn thêm bộ nhớ?"

Đây là bài toán LinkedList Cycle II trên LeetCode. Để giải quyết nó một cách tối ưu với độ phức tạp không gian hằng số $O(1)$, chúng ta không chỉ cần kỹ năng lập trình tốt mà còn cần hiểu một chút toán học đằng sau sự giao nhau của hai con trỏ. Hãy cùng Code O Nhat khám phá nhé!

---

📖 Phân tích đề bài & Ràng buộc

Cho đầu của một danh sách liên kết đơn (head), chúng ta cần trả về đối tượng nút (ListNode) nơi chu trình bắt đầu. Nếu không có chu trình, hãy trả về None.

Lưu ý quan trọng: Không được chỉnh sửa hay thay đổi cấu trúc của danh sách liên kết.

Các ràng buộc:

• Số lượng nút trong danh sách nằm trong khoảng \([0, 10^4]\).

• Giá trị mỗi nút: \(-10^5 \le Node.val \le 10^5\).

• Độ phức tạp thời gian yêu cầu: $O(N)$.

• Độ phức tạp không gian yêu cầu: $O(1)$ auxiliary space (bộ nhớ phụ trợ hằng số).

---

💡 Ý tưởng thuật toán: Từ Thô sơ đến Tối ưu

1. Cách tiếp cận thô sơ: Sử dụng Hash Set

Giống như bài phát hiện chu trình thông thường, chúng ta có thể duyệt qua danh sách và lưu trữ các nút đã đi qua vào một Hash Set. Nút đầu tiên xuất hiện hai lần trong quá trình duyệt chính là điểm bắt đầu của chu trình.

• Độ phức tạp thời gian: $O(N)$

• Độ phức tạp không gian: $O(N)$ (do phải lưu trữ các nút trong tập hợp).

• Hạn chế: Không đạt yêu cầu về không gian bộ nhớ hằng số $O(1)$.

2. Cách tiếp cận tối ưu: Thuật toán Rùa và Thỏ & Phép dịch chuyển toán học

Để giải quyết bài toán với bộ nhớ $O(1)$, chúng ta thực hiện theo hai giai đoạn:

Giai đoạn 1: Phát hiện chu trình

Khởi tạo hai con trỏ tại head:

• slow (Rùa): đi 1 bước mỗi lượt.

• fast (Thỏ): đi 2 bước mỗi lượt.

Nếu chúng gặp nhau ở một nút nào đó (gọi là Điểm Gặp Nhau - Meeting Point), điều đó chứng minh danh sách có chu trình. Nếu fast chạm None, danh sách không có chu trình.

Giai đoạn 2: Tìm điểm bắt đầu chu trình (Toán học chứng minh)

Tại sao khi hai con trỏ gặp nhau, ta lại có thể tìm được điểm bắt đầu? Hãy cùng phân tích các khoảng cách sau:

• Gọi $H$ là khoảng cách từ đầu danh sách (head) đến điểm bắt đầu chu trình.

• Gọi $M$ là khoảng cách từ điểm bắt đầu chu trình đến Điểm Gặp Nhau.

• Gọi $C$ là chiều dài của chu trình.

Khi slow và fast gặp nhau tại Điểm Gặp Nhau:

• Quãng đường slow đã đi: \(S = H + M\)

• Quãng đường fast đã đi: \(F = H + M + k \times C\) (với $k$ là số vòng lặp fast đã chạy trong chu trình).

Vì tốc độ của fast gấp đôi slow, quãng đường đi được cũng gấp đôi: $$F = 2 \times S$$ $$H + M + k \times C = 2 \times (H + M)$$ $$H + M + k \times C = 2H + 2M$$ $$H = k \times C - M$$

Công thức \(H = k \times C - M\) nói lên điều gì? Nó có nghĩa là: Khoảng cách từ đầu danh sách đến điểm bắt đầu chu trình ($H$) đúng bằng quãng đường từ Điểm Gặp Nhau đi tiếp $k$ vòng chu trình trừ đi đoạn $M$.

Do đó, nếu ta đặt một con trỏ mới runner tại head và giữ slow ở Điểm Gặp Nhau, rồi cho cả hai cùng di chuyển với tốc độ 1 bước mỗi lượt, chúng sẽ gặp nhau tại đúng điểm bắt đầu chu trình sau đúng $H$ bước!

---

🚶‍♂️ Minh họa từng bước chạy (State Walkthrough)

Xét danh sách liên kết: [3, 2, 0, -4] với chu trình quay lại nút 2 (chỉ số 1).

• $H$ (từ 3 đến 2) = 1.

• $C$ (chu trình 2 -> 0 -> -4 -> 2) = 3.

Bước 1: Phát hiện điểm gặp nhau

• Ban đầu: slow và fast ở 3.

• Lượt 1: slow = 2, fast = 0.

• Lượt 2: slow = 0, fast = 2 (vòng qua -4 trỏ lại 2).

• Lượt 3: slow = -4, fast = -4 (gặp nhau tại -4).

Bước 2: Tìm điểm bắt đầu

• Đặt runner ở đầu danh sách: runner = 3. Giữ slow = -4.

• Lượt 1: runner = 2 (đi tiếp 1 bước), slow = 2 (từ -4 trỏ đến 2).

• Kết quả: runner == slow tại nút 2. Đây chính là điểm bắt đầu chu trình!

Lượt	runner (giá trị nút)	slow (giá trị nút)	Ghi chú
Khởi tạo	3 (tại head)	-4 (tại điểm gặp)	runner đặt lại head, slow giữ nguyên
1	2	2	runner == slow -> Dừng lại và trả về nút 2

---

🛠️ Cài đặt Python

Dưới đây là mã nguồn Python chi tiết được chú thích rõ ràng:

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

def detect_cycle_start(head: Optional[ListNode]) -> Optional[ListNode]:
    """
    Tìm nút bắt đầu của chu trình trong danh sách liên kết đơn.
    Nếu không có chu trình, trả về None.
    
    Độ phức tạp thời gian: O(N)
    Độ phức tạp không gian: O(1)
    """
    if not head or not head.next:
        return None
        
    slow = head
    fast = head
    
    # Bước 1: Phát hiện chu trình
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if slow == fast:
            break
            
    # Nếu vòng lặp kết thúc mà không gặp nhau thì danh sách không có chu trình
    if slow != fast:
        return None
        
    # Bước 2: Tìm điểm bắt đầu chu trình
    runner = head
    while runner != slow:
        runner = runner.next
        slow = slow.next
        
    return runner

---

📊 Phân tích độ phức tạp

• Độ phức tạp thời gian: $O(N)$

  • Giai đoạn phát hiện chu trình mất tối đa $N$ bước.

  • Giai đoạn tìm điểm bắt đầu mất tối đa \(H \le N\) bước.

  • Tổng thời gian tỷ lệ tuyến tính với số lượng nút trong danh sách: $O(N)$.

• Độ phức tạp không gian bộ nhớ: $O(1)$

  • Chúng ta chỉ cần ba biến con trỏ (slow, fast, runner) để lưu trữ tham chiếu. Bộ nhớ này hoàn toàn độc lập với kích thước danh sách liên kết.

---

🧪 Trường hợp biên & Lưu ý khi phỏng vấn

Khi gặp dạng bài này trong phỏng vấn, hãy luôn kiểm tra và thảo luận các trường hợp sau:

1. Danh sách rỗng hoặc chỉ có 1 nút: Đoạn code trên xử lý an toàn bằng cách trả về None ngay lập tức nhờ điều kiện if not head or not head.next.

2. Chu trình tự lặp lại (Self Cycle): Ví dụ nút duy nhất tự trỏ lại chính nó. Thuật toán hoạt động hoàn hảo và trả về chính nút đó.

3. Giải thích công thức toán học: Đừng chỉ viết code! Việc giải thích logic \(H = k \times C - M\) cho người phỏng vấn nghe sẽ thể hiện sự hiểu biết sâu sắc và tư duy phân tích của bạn.

---

✍️ Kết luận

Thuật toán Rùa và Thỏ không chỉ đơn thuần là việc tăng tốc độ di chuyển con trỏ mà còn mang tính ứng dụng toán học rất cao để giải quyết các cấu trúc tuần hoàn. Việc nắm vững kỹ thuật này giúp bạn dễ dàng xử lý các bài toán nâng cao liên quan đến danh sách liên kết trong các buổi phỏng vấn kỹ thuật.

Bạn đã hiểu rõ logic toán học đằng sau giải thuật này chưa? Hãy để lại ý kiến đóng góp của bạn ở phần bình luận nhé!