Trong singly-linked list, vòng lặp (cycle/loop) là gì?
Trong singly-linked list, vòng lặp (cycle/loop) là gì?
Cycle (vòng) xảy ra khi một nút trỏ ngược về nút trước đó, khiến duyệt không bao giờ gặp null ⇒ lặp vô hạn.
Phát hiện — Floyd (rùa và thỏ): hai con trỏ, chậm đi 1, nhanh đi 2; nếu gặp nhau ⇒ có vòng. O(n) thời gian, O(1) bộ nhớ.
def has_cycle(head):
slow = fast = head
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.