Linked List Cycle

Q: Độ phức tạp về thời gian và bộ nhớ của bài toán chu trình trong danh sách liên kết là bao nhiêu?

Cả hai cách đều mất thời gian O(n) . Đánh dấu các nút đã đi qua cần thêm O(n) bộ nhớ. Cách dùng hai con trỏ nhanh và chậm của Floyd cần O(1) : hai số nút.

DễCon trỏ nhanh và chậm Danh sách liên kết

+10

Danh sách liên kết được lưu trong mảng next: nút i liên kết đến nút next[i], còn -1 nghĩa là danh sách kết thúc tại đó. Nút đầu là nút 0. Đi theo các liên kết từ nút đầu và trả về true nếu bạn quay lại một nút đã đi qua, hoặc false nếu bạn đến cuối danh sách. Những nút mà bạn không đi đến không được tính, ngay cả khi chúng liên kết với nhau thành một vòng lặp.

Hàm

hasCycle(next: integer-array) → boolean

nextinteger-array: liên kết của mỗi nút: next[i] là nút đứng sau nút i hoặc -1
Trả vềboolean: true nếu đường đi từ nút 0 ghé lại một nút đã đi qua, false nếu đến -1

Ràng buộc

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Nhiều nút có thể liên kết đến cùng một nút, và một số nút có thể không thể truy cập được từ nút đầu.

Ví dụ

Đầu vào: next = [1, 2, 3, 1]
Đầu ra: true
Giải thích: Lộ trình đi qua 0, 1, 2, 3 rồi quay lại 1. Nút 1 được ghé thăm hai lần, nên danh sách có một chu trình đi qua các nút 1, 2 và 3.

Đầu vào: next = [2, -1, 1]
Đầu ra: false
Giải thích: Đường đi lần lượt qua 0, 2, 1 rồi đến -1: ba nút khác nhau rồi kết thúc, nên không có chu trình.

Đầu vào: next = [-1, 2, 1]
Đầu ra: false
Giải thích: Nút 0 liên kết với -1, nên danh sách chỉ có một nút. Nút 1 và 2 liên kết với nhau thành một vòng lặp, nhưng khi đi từ nút đầu, bạn không bao giờ đến được chúng.

Câu hỏi mở rộng

Bạn cũng có thể tìm nút nơi chu trình bắt đầu mà vẫn chỉ dùng thêm bộ nhớ O(1) không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Danh sách có chu kỳ sẽ không bao giờ đến -1, nên bạn không thể chờ đến lúc kết thúc. Ghi nhớ mọi nút đã đi qua sẽ phát hiện vòng lặp với bộ nhớ O(n). Hai con trỏ nhanh và chậm của Floyd phát hiện vòng lặp chỉ với hai số nguyên, vì con trỏ di chuyển nhanh gấp đôi chắc chắn sẽ bắt kịp con trỏ chậm bên trong vòng lặp.

Đánh dấu các nút bạn truy cập

Ý tưởng

Bắt đầu đi từ nút 0 và đánh dấu mỗi nút khi bạn rời khỏi đó. Đến một nút đã được đánh dấu nghĩa là bạn đã quay lại, và từ đó hành trình cứ lặp lại mãi. Trong ví dụ 1, bạn đánh dấu các nút 0, 1, 2 và 3, còn nút 3 nối với nút 1, vốn đã được đánh dấu.

Các nút được đánh số từ 0 đến n-1, nên một mảng boolean có độ dài n có thể dùng làm tập hợp các nút đã thăm. Hành trình dừng trong vòng n bước: thời gian O(n) và bộ nhớ O(n) để lưu các dấu đánh dấu.

Thuật toán

Tạo một mảng boolean visited có độ dài n, với tất cả giá trị đều là false.
Đặt node = 0.
Khi node khác -1, trả về true nếu visited[node] đã là true.
Nếu không, đặt visited[node] rồi chuyển đến next[node].
Khi đường đi đến -1, trả về false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Con trỏ nhanh và chậm (phát hiện chu trình của Floyd)

Ý tưởng

slow đi theo một liên kết mỗi lượt, còn fast đi theo hai liên kết. Nếu danh sách kết thúc, fast chạm -1 trước. Nếu có chu trình, fast đi vào chu trình và tiếp tục đi vòng quanh cho đến khi slow đến nơi.

Khi cả hai đã ở trong chu trình, mỗi lượt fast tiến gần hơn slow đúng một nút. Khoảng cách giảm đi một sau mỗi lượt, nên cuối cùng bằng không và hai con trỏ trỏ đến cùng một nút; khoảng cách không thể bỏ qua mức không.

Trong ví dụ 1, sau một lượt, slow ở nút 1 và fast ở nút 2. Sau hai lượt, slow ở nút 2 và fast ở nút 1. Sau ba lượt, cả hai đều ở nút 3.

slow đi vào chu trình trong vòng n lượt, và hai con trỏ gặp nhau trước khi slow đi hết một vòng: thời gian O(n), bộ nhớ dùng hai số nguyên.

Thuật toán

Đặt slow = 0 và fast = 0.
Trong khi fast khác -1 và next[fast] khác -1, di chuyển slow một liên kết và fast hai liên kết.
Sau mỗi lần di chuyển, trả về true nếu chúng ở cùng một nút.
Khi vòng lặp dừng, fast đã tìm thấy điểm cuối: trả về false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Lỗi thường gặp và trường hợp biên

Di chuyển fast nhanh hai liên kết mà không kiểm tra cả hai. fast và next[fast] phải là các nút hợp lệ trước khi bạn đọc next[next[fast]]; nếu không, bạn sẽ đọc next[-1], gây lỗi hoặc trong Python sẽ âm thầm đọc phần tử cuối cùng.
So sánh các con trỏ trước khi di chuyển chúng. Cả hai đều bắt đầu ở nút 0, vì vậy kiểm tra ở đầu vòng lặp sẽ báo có chu trình trong mọi danh sách.
Xem toàn bộ mảng thay vì đường đi. Trong [-1, 2, 1], các nút 1 và 2 tạo thành vòng lặp nằm ngoài tầm với của nút đầu, nên kết quả là false. Giá trị lặp lại cũng không có nghĩa là có chu trình: trong [4, 4, 4, 4, -1], bốn nút liên kết với nút 4.
Cho rằng chu trình phải quay lại nút đầu. Trong [1, 2, 3, 4, 4], nút cuối liên kết với chính nó.

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

Phát hiện chu trình của Floyd hoạt động như thế nào?

Hai con trỏ bắt đầu ở đầu danh sách: một con di chuyển qua một liên kết mỗi bước, con còn lại di chuyển qua hai liên kết. Nếu không có chu trình, con trỏ nhanh sẽ đến cuối danh sách. Nếu có chu trình, cả hai sẽ đi vào trong chu trình, con trỏ nhanh rút ngắn khoảng cách một nút mỗi bước, và hai con trỏ gặp nhau tại cùng một nút.

Độ phức tạp về thời gian và bộ nhớ của bài toán chu trình trong danh sách liên kết là bao nhiêu?

Cả hai cách đều mất thời gian O(n). Đánh dấu các nút đã đi qua cần thêm O(n) bộ nhớ. Cách dùng hai con trỏ nhanh và chậm của Floyd cần O(1): hai số nút.

Bạn có thể phát hiện chu trình bằng tập hợp băm không?

Có. Với danh sách liên kết gồm các đối tượng, hãy đưa tham chiếu của mỗi nút vào một tập hợp băm và báo có chu trình nếu tham chiếu đó đã có trong tập hợp. Cách này chạy trong O(n) thời gian nhưng dùng O(n) bộ nhớ, vì vậy người phỏng vấn tiếp theo sẽ yêu cầu bạn dùng thuật toán Floyd.

Bạn có thể phát hiện chu kỳ bằng cách đếm số bước không?

Với dạng mảng này thì đúng: danh sách không có chu trình sẽ đến -1 trong vòng n liên kết, nên nếu đi qua n liên kết mà vẫn chưa đến cuối thì chứng tỏ có chu trình. Danh sách gồm các con trỏ không cho bạn biết n, còn việc đếm các nút trước sẽ không bao giờ kết thúc nếu có chu trình.

def hasCycle(next):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

next = [1, 2, 3, 1]

Đầu ra mong đợi

true