Thuật toán tìm chu trình trong danh sách liên kết của Floyd (Floyd's Linked List Cycle Finding Algorithm)¶
Cho một danh sách liên kết trong đó điểm bắt đầu của danh sách liên kết đó được ký hiệu là head, và có thể có hoặc không có chu trình. Ví dụ:
Ở đây chúng ta cần tìm điểm C, tức là điểm bắt đầu của chu trình.
Thuật toán đề xuất (Proposed algorithm)¶
Thuật toán này được gọi là Thuật toán chu trình Floyd (Floyd’s Cycle Algorithm) hoặc Thuật toán Rùa và Thỏ (Tortoise And Hare algorithm). Để tìm ra điểm bắt đầu của chu trình, chúng ta cần tìm xem chu trình có tồn tại hay không. Điều này bao gồm hai bước: 1. Tìm ra sự hiện diện của chu trình. 2. Tìm ra điểm bắt đầu của chu trình.
Bước 1: Sự hiện diện của chu trình (Step 1: Presence of the cycle)¶
- Lấy hai con trỏ $slow$ (chậm) và $fast$ (nhanh).
- Ban đầu cả hai sẽ trỏ đến head của danh sách liên kết.
- $slow$ sẽ di chuyển từng bước một.
- $fast$ sẽ di chuyển hai bước một lúc. (tốc độ gấp đôi con trỏ $slow$).
- Kiểm tra xem liệu tại bất kỳ thời điểm nào chúng có trỏ đến cùng một nút trước khi bất kỳ ai (hoặc cả hai) chạm tới null hay không.
- Nếu chúng trỏ đến cùng một nút tại bất kỳ điểm nào trong hành trình của chúng, điều đó cho thấy rằng một chu trình thực sự tồn tại trong danh sách liên kết.
- Nếu chúng ta nhận được null, điều đó cho thấy danh sách liên kết không có chu trình.
Bây giờ chúng ta đã tìm ra nếu có một chu trình hiện diện trong danh sách liên kết, bước tiếp theo chúng ta cần tìm ra điểm bắt đầu của chu trình, tức là C.
Bước 2: Điểm bắt đầu của chu trình (Step 2: Starting point of the cycle)¶
- Đặt lại con trỏ $slow$ về head của danh sách liên kết.
- Di chuyển cả hai con trỏ từng bước một.
- Điểm mà chúng gặp nhau sẽ là điểm bắt đầu của chu trình.
// Presence of cycle
public boolean 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;
}
// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
slow = slow.next;
fast = fast.next;
}
return slow; // the starting point of the cycle.
Tại sao nó hoạt động (Why does it work)¶
Bước 1: Sự hiện diện của chu trình (Step 1: Presence of the cycle)¶
Vì con trỏ $fast$ di chuyển với tốc độ gấp đôi $slow$, chúng ta có thể nói rằng tại bất kỳ thời điểm nào, $fast$ sẽ đi được quãng đường gấp đôi $slow$. Chúng ta cũng có thể suy ra rằng sự khác biệt giữa khoảng cách đi được của cả hai con trỏ này đang tăng lên $1$.
slow: 0 --> 1 --> 2 --> 3 --> 4 (distance covered)
fast: 0 --> 2 --> 4 --> 6 --> 8 (distance covered)
diff: 0 --> 1 --> 2 --> 3 --> 4 (difference between distance covered by both pointers)
Bước 2: Điểm bắt đầu của chu trình (Step 2: Starting point of the cycle)¶
Hãy thử tính khoảng cách đi được của cả hai con trỏ cho đến khi chúng gặp nhau trong chu trình.
$slowDist = a + xL + b$ , $x\ge0$
$fastDist = a + yL + b$ , $y\ge0$
- $slowDist$ là tổng khoảng cách đi được bởi con trỏ chậm.
- $fastDist$ là tổng khoảng cách đi được bởi con trỏ nhanh.
- $a$ là số bước mà cả hai con trỏ cần thực hiện để vào chu trình.
- $b$ là khoảng cách giữa C và G, tức là khoảng cách giữa điểm bắt đầu của chu trình và điểm gặp nhau của cả hai con trỏ.
- $x$ là số lần con trỏ chậm đã lặp bên trong chu trình, bắt đầu từ và kết thúc tại C.
- $y$ là số lần con trỏ nhanh đã lặp bên trong chu trình, bắt đầu từ và kết thúc tại C.
$fastDist = 2 \cdot (slowDist)$
$a + yL + b = 2(a + xL + b)$
Giải quyết công thức chúng ta nhận được:
$a=(y-2x)L-b$
trong đó $y-2x$ là một số nguyên
Về cơ bản, điều này có nghĩa là $a$ bước giống như thực hiện một số vòng lặp đầy đủ trong chu trình và đi ngược lại $b$ bước. Vì con trỏ nhanh đã đi trước $b$ bước so với lối vào của chu trình, nếu con trỏ nhanh di chuyển thêm $a$ bước nữa, nó sẽ kết thúc tại lối vào của chu trình. Và vì chúng ta để con trỏ chậm bắt đầu từ đầu danh sách liên kết, sau $a$ bước, nó cũng sẽ kết thúc tại lối vào chu trình. Vì vậy, nếu cả hai di chuyển $a$ bước, cả hai sẽ gặp lối vào của chu trình.