Phỏng vấn

Con trỏ nhanh chậm (Fast & Slow Pointers) và thuật toán Floyd

Kỹ thuật con trỏ nhanh chậm (Fast & Slow Pointers) cho phép phát hiện chu trình, tìm đúng nút bắt đầu vòng lặp và xác định trung điểm danh sách liên kết chỉ với bộ nhớ phụ O(1). Hiểu rõ đẳng thức khoảng cách của thuật toán rùa và thỏ Floyd sẽ giúp bạn giải thích trôi chảy phần chứng minh trước người phỏng vấn.

Bài toán chu trình trên danh sách liên kết và các câu hỏi làm rõ đề

Trên cấu trúc mảng tĩnh, bạn có thể nhảy tới phần tử giữa bằng chỉ số n / 2 trong O(1) hoặc kiểm tra trạng thái dễ dàng. Ngược lại, trên danh sách liên kết đơn (singly linked list), ta không biết trước độ dài n và cũng không thể đi lùi. Nếu con trỏ next của một nút ở cuối danh sách vô tình trỏ ngược về một nút phía trước, việc duyệt tuần tự sẽ rơi vào vòng lặp vô tận.

Khi gặp các câu hỏi phỏng vấn như Linked List Cycle, Linked List Cycle II (tìm nút bắt đầu chu trình), Middle of the Linked List hay Find the Duplicate Number, bạn nên làm rõ ngay với người phỏng vấn bốn ràng buộc sau:

  • Giới hạn bộ nhớ phụ: Nếu được phép dùng O(n) bộ nhớ phụ, việc lưu địa chỉ các nút đã thăm vào một HashSet sẽ giải quyết bài toán phát hiện chu trình ngay lập tức. Tuy nhiên, hầu hết người phỏng vấn sẽ đặt điều kiện theo sau (follow-up): "Em hãy giải với bộ nhớ phụ O(1) và không được làm hỏng cấu trúc con trỏ next của danh sách."
  • Quy ước nút giữa khi số nút chẵn: Với danh sách có 6 nút 0 -> 1 -> 2 -> 3 -> 4 -> 5, có hai nút đứng giữa là nút chỉ số 2 (trung điểm thứ nhất) và nút chỉ số 3 (trung điểm thứ hai). Đề bài yêu cầu trả về nút nào? (Chẳng hạn khi tách đôi danh sách cho thuật toán Merge Sort trên Linked List, ta thường cần dừng ở trung điểm thứ nhất để ngắt liên kết; còn bài Middle of the Linked List chuẩn lại yêu cầu trung điểm thứ hai).
  • Giá trị trên các nút có duy nhất không? Bạn cần khẳng định rõ chu trình được định nghĩa theo địa chỉ vùng nhớ của nút (node reference) chứ không phải theo giá trị val lưu bên trong nút, vì nhiều nút khác nhau hoàn toàn có thể mang cùng một số nguyên.
  • Trường hợp danh sách rỗng hoặc chỉ có 1 nút: Danh sách head == null hoặc một nút tự trỏ vào chính nó (pos = 0) có xuất hiện trong bộ kiểm thử không?
Ý chính

Thuật toán rùa và thỏ của Robert W. Floyd dùng hai con trỏ cùng xuất phát từ head: con trỏ chậm slow mỗi bước tiến 1 nút, con trỏ nhanh fast mỗi bước tiến 2 nút. Nếu danh sách có chu trình độ dài C, một khi cả hai đã vào trong vòng lặp thì mỗi bước khoảng cách từ fast đuổi theo slow giảm đi đúng 1 đơn vị, nên chúng bắt buộc phải gặp nhau mà không bao giờ nhảy vọt qua nhau.

Thuật toán Floyd tìm chu trình: 3 → 2 → 0 → -4 (quay về nút 2) 3 idx 0 2 idx 1 (cửa) 0 idx 2 -4 idx 3 (gặp) Chu trình C = 3 nút: next(-4) trỏ ngược về nút 2 (idx 1) Pha 1: slow (+1), fast (+2) Gặp nhau tại idx 3 (giá trị -4) Pha 2: p1 từ idx 0, p2 từ idx 3 (+1) Chạm nhau tại cửa chu trình idx 1 (val 2) Thời gian O(n) · Bộ nhớ phụ O(1) (không dùng bảng băm)
Floyd Cycle: 3 → 2 → 0 → -4 ↺ Đoạn dẫn L = 1 · Chu trình C = 3 (quay về 2) idx 0: val 3 Đầu danh sách idx 1: val 2 Cửa chu trình! idx 2: val 0 Trong chu trình idx 3: val -4 Điểm gặp Pha 1 Pha 1: slow (+1), fast (+2) gặp ở idx 3 Pha 2: p1 từ 0, p2 từ 3 (+1) gặp ở idx 1 Thời gian O(n) · Bộ nhớ phụ O(1)
Hình 1. Hai pha của thuật toán Floyd trên danh sách 3 -> 2 -> 0 -> -4 quay vòng về nút 2 (chỉ số 1): Pha 1 gặp nhau tại nút -4 (chỉ số 3), Pha 2 tìm đúng điểm đầu chu trình tại nút 2 (chỉ số 1).

Chứng minh toán học vì sao Pha 2 tìm đúng nút đầu chu trình

Trong phỏng vấn cấp độ Mid/Senior tại các công ty công nghệ lớn, viết được code Pha 1 và Pha 2 mới chỉ đạt một nửa yêu cầu; người phỏng vấn gần như chắc chắn sẽ hỏi: "Tại sao sau khi slow và fast gặp nhau, việc đặt một con trỏ về head rồi cho cả hai cùng đi từng bước lại chạm nhau đúng ở cửa vào chu trình?" Bạn có thể trình bày lời giải thích ngắn gọn chỉ bằng ba ký hiệu:

  • Gọi \(L\) là số bước từ đầu danh sách head tới nút bắt đầu chu trình (cửa vào vòng lặp).
  • Gọi \(C\) là chu vi của chu trình (số nút nằm trong vòng lặp).
  • Gọi \(x\) (\(0 \le x < C\)) là số bước tính từ cửa vào chu trình đi theo chiều mũi tên tới điểm gặp nhau của slow và fast ở cuối Pha 1.

Khi hai con trỏ gặp nhau sau \(t\) bước di chuyển:

  • Con trỏ chậm slow đã đi được quãng đường là \(t = L + x\) (vì ngay trong vòng đầu tiên sau khi slow bước vào chu trình, fast với vận tốc gấp đôi đã kịp đuổi kịp slow trước khi slow đi hết một vòng \(C\)).
  • Con trỏ nhanh fast đã đi được quãng đường gấp đôi là \(2t\), đồng thời nó đã đi qua đoạn thẳng \(L\), đi thêm đoạn \(x\) và quay thêm một số nguyên \(k \ge 1\) vòng quanh chu trình:

\[2(L + x) = L + x + kC \implies L + x = kC \implies L = kC - x = (k - 1)C + (C - x)\]

Đẳng thức \(L = (k - 1)C + (C - x)\) mang ý nghĩa hình học cực kỳ trực quan:

  • Nếu con trỏ p1 xuất phát từ head và đi thẳng \(L\) bước, nó sẽ dừng ngay tại cửa vào chu trình.
  • Cùng lúc đó, nếu con trỏ p2 xuất phát từ điểm gặp nhau (đang cách cửa vào một đoạn \(x\) theo chiều thuận, tức là còn cách cửa vào đúng \(C - x\) bước nữa để khép kín vòng), sau khi đi \(L = (k - 1)C + (C - x)\) bước, nó sẽ đi tiếp phần còn lại \(C - x\) để chạm cửa vào chu trình rồi quay thêm \(k - 1\) vòng nguyên nữa và dừng đúng tại cửa vào chu trình!

Do đó, điểm đầu tiên mà p1 và p2 chạm mặt nhau bắt buộc phải là nút mở đầu chu trình.

Chạy tay từng bước trên danh sách 4 nút pos = 1 và danh sách không chu trình

Xét danh sách có 4 nút đánh chỉ số 0, 1, 2, 3 với giá trị lần lượt là 3 -> 2 -> 0 -> -4, trong đó nút cuối chỉ số 3 (giá trị -4) có con trỏ next quay về nút chỉ số 1 (giá trị 2). Như vậy \(L = 1\) (từ chỉ số 0 sang 1) và chu vi vòng lặp là \(C = 3\) (gồm các nút 1 -> 2 -> 3 -> 1).

Pha và bước Vị trí slow / p1 Vị trí fast / p2 Kiểm tra điều kiện Giải thích trạng thái
Pha 1 — Khởi tạo slow = 0 (val 3) fast = 0 (val 3) Bắt đầu vòng lặp Cả hai cùng xuất phát tại head (chỉ số 0)
Pha 1 — Bước 1 slow = 1 (val 2) fast = 2 (val 0) slow != fast slow vừa chạm cửa vào vòng; fast nhảy 0 -> 1 -> 2
Pha 1 — Bước 2 slow = 2 (val 0) fast = 1 (2 -> 3 -> 1) slow != fast fast đi qua đáy -4 (chỉ số 3) và vòng lại chỉ số 1
Pha 1 — Bước 3 slow = 3 (val -4) fast = 3 (1 -> 2 -> 3) slow == fast == 3 Gặp nhau tại chỉ số 3! Kết thúc Pha 1 (\(x = 2\), \(C - x = 1\))
Pha 2 — Khởi tạo p1 = 0 (val 3) p2 = 3 (val -4) p1 != p2 Đặt p1 về head (0), giữ p2 tại điểm gặp (3)
Pha 2 — Bước 1 p1 = 1 (val 2) p2 = 1 (3 -> 1) p1 == p2 == 1 Chạm nhau tại chỉ số 1! Trả về nút đầu chu trình 1

Với danh sách không có chu trình (pos = -1), chẳng hạn n = 5 nút 0 -> 1 -> 2 -> 3 -> 4 -> null, ta dùng cùng mô hình con trỏ nhanh chậm để tìm nút giữa:

  • Khởi đầu: slow = 0, fast = 0.
  • Bước 1: slow = 1, fast = 2.
  • Bước 2: slow = 2, fast = 4. Lúc này fast đã ở nút cuối (fast.next == null) nên dừng vòng lặp, trả về slow = 2 (đúng trung điểm của 5 nút).
  • Nếu n = 6 nút 0..5: sau Bước 2 (slow = 2, fast = 4), vì vẫn còn nút chỉ số 5 phía sau nên bước thêm một nhịp nữa để slow = 3 (trung điểm thứ hai) và fast vượt ra cuối danh sách.

Code mẫu C++17, Python và Java 21

Để dễ dàng kiểm thử độc lập từ dòng lệnh mà không phụ thuộc vào bộ cấp phát con trỏ thô, chương trình dưới đây biểu diễn danh sách liên kết gồm n nút 0..n-1 thông qua mảng chuyển tiếp next_idx (tương đương trường .next của mỗi nút) cùng tham số pos chỉ định nút mà đuôi danh sách nối về (pos = -1 nếu danh sách thẳng không có chu trình). Chương trình in ra hai số: chỉ số nút giữa (khi pos == -1, ngược lại in -1) và chỉ số nút bắt đầu chu trình (hoặc -1 nếu không có chu trình).

#include <iostream>
#include <vector>
using namespace std;

int detect_cycle_entry(const vector<int>& next_idx) {
    int slow = 0, fast = 0;
    while (fast != -1 && next_idx[fast] != -1) {
        slow = next_idx[slow];
        fast = next_idx[next_idx[fast]];
        if (slow == fast) {
            int p1 = 0, p2 = slow;
            while (p1 != p2) {
                p1 = next_idx[p1];
                p2 = next_idx[p2];
            }
            return p1;
        }
    }
    return -1;
}

int middle_node(const vector<int>& next_idx) {
    int slow = 0, fast = 0;
    while (fast != -1 && next_idx[fast] != -1) {
        slow = next_idx[slow];
        fast = next_idx[next_idx[fast]];
    }
    return slow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 4, pos = 1;
    if (!(cin >> n >> pos)) {
        n = 4;
        pos = 1;
    }
    if (n == 0) {
        cout << "-1 -1\n";
        return 0;
    }
    vector<int> next_idx(n, -1);
    for (int i = 0; i + 1 < n; i++) next_idx[i] = i + 1;
    if (pos >= 0 && pos < n) next_idx[n - 1] = pos;
    int mid = (pos == -1) ? middle_node(next_idx) : -1;
    int entry = detect_cycle_entry(next_idx);
    cout << mid << ' ' << entry << '\n';
    return 0;
}

Độ phức tạp và lưu ý cài đặt

  • Thời gian: O(n).
    • Khi không có chu trình, vòng lặp dừng sau đúng \(\lfloor n/2 \rfloor\) bước: với n chẵn fast thành null, với n lẻ fast dừng ở nút cuối vì fast.next == null.
    • Khi có chu trình, slow đi \(L\) bước để vào vòng và đi thêm \(x < C\) bước trước khi gặp fast, nên Pha 1 tốn \(L + x < n\) bước. Pha 2 tốn đúng \(L\) bước nữa. Tổng số bước luôn nhỏ hơn \(2n\), tức O(n).
  • Bộ nhớ phụ: O(1) trên danh sách liên kết thật vì thuật toán chỉ giữ các biến con trỏ slow, fast, p1, p2 mà không cấp phát thêm bất kỳ tập hợp hay mảng đánh dấu nào.

Các biến thể mở rộng của mẫu con trỏ nhanh chậm

Kỹ thuật rùa và thỏ vượt xa phạm vi danh sách liên kết đơn thuần và xuất hiện dưới nhiều lớp vỏ bọc thú vị trong phỏng vấn:

Bài toán Cách ánh xạ về đồ thị hàm bậc ra bằng 1 (\(f(u)\)) Điểm cần chú ý khi cài đặt
Linked List Cycle I & II Mỗi nút u có đúng một cung đi tới u.next Kiểm tra kỹ fast != null && fast.next != null trước khi nhảy fast.next.next
Find the Duplicate Number (Mảng n + 1 số thuộc [1..n]) Xem mỗi chỉ số i là một đỉnh có mũi tên trỏ sang đỉnh nums[i] Vì không có phần tử nào bằng 0, đỉnh 0 có bậc vào bằng 0 nên chắc chắn nằm ngoài chu trình; số bị lặp có ít nhất hai chỉ số trỏ tới nên chính là cửa vào chu trình
Happy Number (Tổng bình phương các chữ số) Từ số \(x\), đỉnh kế tiếp là \(f(x) = \sum d_i^2\) Quá trình luôn giảm về số nhỏ rồi rơi vào điểm bất động \(1 \to 1\) hoặc chu trình \(4 \to 16 \to 37 \to \dots \to 4\); dùng slow/fast không cần HashSet
Palindrome Linked List (Kiểm tra đối xứng O(1) bộ nhớ) Dùng slow/fast tìm trung điểm, đảo ngược nửa sau tại chỗ rồi so sánh hai đầu Sau khi so sánh xong nên đảo ngược lại nửa sau để trả danh sách về nguyên trạng ban đầu
Reorder List / Sort List (Merge Sort) Tìm nút cuối của nửa đầu để cắt danh sách thành hai nửa cân bằng Khởi tạo fast = head.next (hoặc dừng sớm 1 nhịp) để với n chẵn slow dừng ở trung điểm thứ nhất, tránh đệ quy vô hạn khi n = 2

Các lỗi hay gặp trong phòng phỏng vấn và cách tự kiểm tra

  1. Truy cập con trỏ rỗng (NullPointerException / Segmentation fault) khi nhảy hai bước: Viết while (fast != null) rồi bên trong gọi ngay fast = fast.next.next sẽ sập chương trình khi danh sách có số nút lẻ (fast đang ở nút cuối cùng nên fast.next là null). Điều kiện canh gác bắt buộc phải là while (fast != null && fast.next != null).
  2. Đặt điều kiện vòng lặp while (slow != fast) ngay từ đầu khi cả hai cùng khởi tạo bằng head: Vì lúc bắt đầu slow == fast == head, vòng while (slow != fast) sẽ không chạy bước nào cả! Bạn phải di chuyển slow và fast trước rồi mới kiểm tra if (slow == fast) ở cuối thân vòng lặp while.
  3. Khởi tạo lệch vị trí trong Pha 1 (slow = head, fast = head.next): Cách khởi tạo này vẫn phát hiện được có chu trình hay không, nhưng làm lệch công thức khoảng cách thêm 1 bước nên nếu sang Pha 2 bạn đặt p1 = head, p2 = slow như bình thường thì hai con trỏ sẽ lệch nhau và không gặp đúng cửa vào chu trình. Hãy luôn khởi tạo cả slow và fast tại đúng head khi cần tìm điểm đầu chu trình.
  4. Cắt đôi danh sách 2 nút bị lặp vô tận trong Merge Sort: Với danh sách 2 nút 0 -> 1, nếu bạn trả về trung điểm thứ hai (nút 1) làm điểm cuối nửa đầu, hai nửa sau khi chia sẽ có kích thước 2 và 0, làm hàm đệ quy sortList gọi lại chính nó trên 2 nút tới tràn ngăn xếp.

Khi tự kiểm tra code trên giấy hoặc máy tính, bạn hãy chạy thử 5 trường hợp biên nhỏ nhưng bắt trọn mọi nhánh rẽ:

  • Danh sách rỗng n = 0 và danh sách 1 nút không chu trình n = 1, pos = -1.
  • Danh sách 1 nút tự nối vào chính nó (n = 1, pos = 0 → cửa vào chu trình là 0, \(L = 0, C = 1\)).
  • Danh sách mà chu trình bắt đầu ngay tại head (n = 3, pos = 0 → p1 và p2 gặp nhau ngay trước khi vòng lặp Pha 2 kịp chạy bước nào).
  • Danh sách chẵn nút (n = 6, pos = -1) và lẻ nút (n = 5, pos = -1) để đối chiếu vị trí nút giữa.

Luyện ngay trên Big-O Coding

Hãy áp dụng ngay kỹ thuật con trỏ nhanh chậm và các thao tác con trỏ danh sách liên kết qua 3 bài tập chọn lọc trong lộ trình Coding Interview 150 dưới đây.

Câu hỏi thường gặp

Tại sao con trỏ nhanh lại bước 2 bước mỗi lần mà không phải 3 bước hay 4 bước?

Bước 2 nút là lựa chọn duy nhất đảm bảo khi fast đuổi theo slow trong chu trình, khoảng cách giữa chúng giảm đi đúng 1 đơn vị sau mỗi nhịp. Nhờ vậy, khi khoảng cách giảm về 0, hai con trỏ chắc chắn đứng cùng một nút. Nếu fast bước 3 nút mỗi lần, khoảng cách giảm 2 đơn vị mỗi nhịp nên fast có thể nhảy vọt qua slow. Khi cả hai cùng xuất phát từ head thì chúng vẫn gặp nhau, thậm chí không muộn hơn tốc độ 2; nhưng lúc gặp chỉ có \(2t = kC\) chứ không phải \(t = kC\), nên chứng minh ở Pha 2 không còn đúng: với chu trình độ dài chẵn, đặt p1 về head rồi cho hai con trỏ cùng đi từng bước có thể không bao giờ gặp nhau. Ví dụ danh sách 2 nút 0 -> 1 -> 0: tốc độ 3 gặp ở nút 1 ngay nhịp đầu, sau đó p1 và p2 cứ đổi chỗ cho nhau giữa nút 0 và nút 1 mãi mãi. Tổng quát, với fast bước v nút thì lúc gặp chỉ có \((v - 1)t = kC\), và chỉ \(v = 2\) mới bảo đảm \(t = kC\).

Làm sao tính được độ dài C của chu trình sau khi hai con trỏ đã gặp nhau?

Ngay tại thời điểm slow == fast ở cuối Pha 1, bạn chỉ cần giữ nguyên slow đứng yên tại chỗ và cho một con trỏ phụ cur = slow.next đi từng bước một (mỗi bước tăng biến đếm len lên 1) cho tới khi cur quay lại chạm slow. Giá trị len thu được chính là chu vi \(C\) của chu trình trong thời gian \(O(C)\) và bộ nhớ \(O(1)\).

Thuật toán Floyd có làm thay đổi hay làm hỏng danh sách liên kết đầu vào không?

Hoàn toàn không. Khác với mẹo đánh dấu bằng cách gán tạm node.next = dummy (vừa phá vỡ cấu trúc danh sách vừa gây lỗi nếu dữ liệu nằm trong vùng nhớ chỉ đọc hoặc đa luồng), thuật toán Floyd chỉ đọc trường next mà không ghi đè bất kỳ con trỏ nào của danh sách.

Muốn học bài bản cùng giảng viên?

Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.

Xem Khóa LeetCode

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483