Chương trình Python để phát hiện chu kỳ trong danh sách được liên kết

Khi được yêu cầu phát hiện một chu trình trong danh sách liên kết, một phương pháp để thêm phần tử vào danh sách liên kết và một phương thức để lấy phần tử trong danh sách liên kết được xác định. Một phương pháp khác được định nghĩa để kiểm tra xem giá trị đầu và giá trị phía sau có giống nhau hay không. Dựa trên kết quả này, các chu kỳ được phát hiện.

Dưới đây là một minh chứng cho điều tương tự -

Ví dụ

class Node:
   def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList_structure:
   def __init__(self):
      self.head = None
      self.last_node = None

   def add_vals(self, data):
      if self.last_node is None:
         self.head = Node(data)
         self.last_node = self.head
      else:
         self.last_node.next = Node(data)
         self.last_node = self.last_node.next

def get_node_val(self, index):
   curr = self.head
   for i in range(index):
      curr = curr.next
      if curr is None:
         return None
      return curr

def check_cycle(my_list):
   slow_val = my_list.head
   fast_val = my_list.head
   while (fast_val != None and fast_val.next != None):
      slow_val = slow_val.next
      fast_val = fast_val.next.next
      if slow_val == fast_val:
         return True
      return False

my_linked_list = LinkedList_structure()
my_list = input('Enter the elements in the linked list ').split()
   for elem in my_list:
my_linked_list.add_vals(int(elem))
my_len = len(my_list)
if my_len != 0:
   vals = '0-' + str(my_len - 1)
   last_ptr = input('Enter the index [' + vals + '] of the node' ' at which the last node has to point'' (Enter nothing to point to None): ').strip()
   if last_ptr == '':
      last_ptr = None
   else:
      last_ptr = my_linked_list.get_node_val(int(last_ptr))
      my_linked_list.last_node.next = last_ptr

if check_cycle(my_linked_list):
   print("The linked list has a cycle")
else:
   print("The linked list doesn't have a cycle")

Đầu ra

Enter the elements in the linked list 56 78 90 12 4
Enter the index [0-4] of the node at which the last node has to point (Enter nothing to point to
None):
The linked list doesn't have a cycle

Giải thích

• Lớp 'Node' được tạo.

• Một lớp ‘LinkedList_ architects’ khác với các thuộc tính bắt buộc được tạo.

• Nó có chức năng ‘init’ được sử dụng để khởi tạo phần tử đầu tiên, tức là ‘head’ thành ‘None’.

• Một phương thức có tên là ‘add_vals’ được xác định, giúp thêm một giá trị vào ngăn xếp.

• Một phương thức khác có tên là ‘get_node_val’ được xác định, giúp nhận giá trị của nút hiện tại trong danh sách được liên kết.

• Một phương thức khác có tên là ‘check_cycle’ được định nghĩa, giúp tìm xem phần đầu và phần sau có giống nhau hay không, có nghĩa là đây sẽ là một chu kỳ.

• Nó trả về True hoặc False tùy thuộc vào sự hiện diện hay vắng mặt của chu trình.

• Một phiên bản của ‘LinkedList_ architects’ được tạo.

• Các phần tử được thêm vào danh sách liên kết.

• Phương thức ‘check_cycle’ được gọi trong danh sách được liên kết này.

• Đầu ra được hiển thị trên bảng điều khiển.