Hãy xem xét chúng ta có một danh sách liên kết và chúng ta phải kiểm tra xem có chu kỳ nào hay không. Để biểu diễn chu trình trong danh sách liên kết đã cho, chúng ta sẽ sử dụng một con trỏ số nguyên được gọi là pos. Vị trí này đại diện cho một vị trí trong danh sách liên kết nơi đuôi được kết nối. Vì vậy, nếu pos là -1, thì không có chu trình nào hiện diện trong danh sách liên kết. Ví dụ:danh sách được liên kết giống như [5, 3, 2, 0, -4, 7] và pos =1. Vì vậy, có một chu kỳ và đuôi được kết nối với nút thứ hai.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Lấy một bộ làm bộ băm H
- while head không rỗng -
- nếu head có ở H, thì trả về true
- thêm đầu vào H
- head:=tiếp theo của head
- trả về Sai
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class ListNode: def __init__(self, data, next = None): self.data = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def get_node(head, pos): if pos != -1: p = 0 ptr = head while p < pos: ptr = ptr.next p += 1 return ptr class Solution(object): def hasCycle(self, head): hashS = set() while head: if head in hashS: return True hashS.add(head) head = head.next return False head = make_list([5,3,2,0,-4,7]) last_node = get_node(head, 5) pos = 1 last_node.next = get_node(head, pos) ob1 = Solution() print(ob1.hasCycle(head))
Đầu vào
List = [5,3,2,0,-4,7] Pos = 1
Đầu ra
True