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ộtHashSetsẽ 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ỏnextcủa danh sách." - Quy ước nút giữa khi số nút chẵn: Với danh sách có
6nút0 -> 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ị
vallư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 == nullhoặ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?
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.
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
headtớ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
slowvà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 khislowbước vào chu trình,fastvới vận tốc gấp đôi đã kịp đuổi kịpslowtrước khislowđ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ỏ
p1xuất phát từheadvà đ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ỏ
p2xuấ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àyfastđã ở 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 = 6nút0..5: sau Bước 2 (slow = 2, fast = 4), vì vẫn còn nút chỉ số5phía sau nên bước thêm một nhịp nữa đểslow = 3(trung điểm thứ hai) vàfastvượ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;
}
import sys
def detect_cycle_entry(next_idx: list[int]) -> int:
slow = fast = 0
while fast != -1 and next_idx[fast] != -1:
slow = next_idx[slow]
fast = next_idx[next_idx[fast]]
if slow == fast:
p1, p2 = 0, slow
while p1 != p2:
p1 = next_idx[p1]
p2 = next_idx[p2]
return p1
return -1
def middle_node(next_idx: list[int]) -> int:
slow = fast = 0
while fast != -1 and next_idx[fast] != -1:
slow = next_idx[slow]
fast = next_idx[next_idx[fast]]
return slow
def main() -> None:
data = list(map(int, sys.stdin.buffer.read().split()))
n, pos = (data[0], data[1]) if len(data) >= 2 else (4, 1)
if n == 0:
print("-1 -1")
return
next_idx = [i + 1 for i in range(n - 1)] + [-1]
if 0 <= pos < n:
next_idx[n - 1] = pos
mid = middle_node(next_idx) if pos == -1 else -1
entry = detect_cycle_entry(next_idx)
print(f"{mid} {entry}")
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
static int detectCycleEntry(int[] nextIdx) {
int slow = 0, fast = 0;
while (fast != -1 && nextIdx[fast] != -1) {
slow = nextIdx[slow];
fast = nextIdx[nextIdx[fast]];
if (slow == fast) {
int p1 = 0, p2 = slow;
while (p1 != p2) {
p1 = nextIdx[p1];
p2 = nextIdx[p2];
}
return p1;
}
}
return -1;
}
static int middleNode(int[] nextIdx) {
int slow = 0, fast = 0;
while (fast != -1 && nextIdx[fast] != -1) {
slow = nextIdx[slow];
fast = nextIdx[nextIdx[fast]];
}
return slow;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = 4, pos = 1;
if (sc.hasNextInt()) {
n = sc.nextInt();
pos = sc.nextInt();
}
if (n == 0) {
System.out.println("-1 -1");
return;
}
int[] nextIdx = new int[n];
Arrays.fill(nextIdx, -1);
for (int i = 0; i + 1 < n; i++) nextIdx[i] = i + 1;
if (pos >= 0 && pos < n) nextIdx[n - 1] = pos;
int mid = (pos == -1) ? middleNode(nextIdx) : -1;
int entry = detectCycleEntry(nextIdx);
System.out.println(mid + " " + entry);
}
}
Độ 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
nchẵnfastthànhnull, vớinlẻfastdừ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ặpfast, 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ứcO(n).
- Khi không có chu trình, vòng lặp dừng sau đúng \(\lfloor n/2 \rfloor\) bước: với
- 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,p2mà 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
- Truy cập con trỏ rỗng (
NullPointerException/Segmentation fault) khi nhảy hai bước: Viếtwhile (fast != null)rồi bên trong gọi ngayfast = fast.next.nextsẽ sập chương trình khi danh sách có số nút lẻ (fastđang ở nút cuối cùng nênfast.nextlànull). Điều kiện canh gác bắt buộc phải làwhile (fast != null && fast.next != null). - Đặ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ằnghead: Vì lúc bắt đầuslow == fast == head, vòngwhile (slow != fast)sẽ không chạy bước nào cả! Bạn phải di chuyểnslowvàfasttrước rồi mới kiểm traif (slow == fast)ở cuối thân vòng lặpwhile. - 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 đặtp1 = head, p2 = slownhư 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ảslowvàfasttại đúngheadkhi cần tìm điểm đầu chu trình. - 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út1) làm điểm cuối nửa đầu, hai nửa sau khi chia sẽ có kích thước2và0, làm hàm đệ quysortListgọ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 = 0và danh sách 1 nút không chu trìnhn = 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→p1vàp2gặ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.
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.


