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

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

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 is not None and fast_val.next is not 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('Nhập các phần tử trong danh sách liên kết: ').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('Nhập chỉ số [' + vals + '] của nút mà nút cuối phải trỏ đến (Để trống để trỏ đến 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("Danh sách liên kết có chu trình")
else:
    print("Danh sách liên kết không có chu trình")

Kết quả

Nhập các phần tử trong danh sách liên kết: 56 78 90 12 4
Nhập chỉ số [0-4] của nút mà nút cuối phải trỏ đến (Để trống để trỏ đến None): 
Danh sách liên kết không có chu trình

Giải thích

• Lớp Node được tạo.
• Lớp LinkedList_structure với các thuộc tính cần thiết được tạo.
• Phương thức __init__ khởi tạo phần tử đầu tiên (head) là None.
• Phương thức add_vals giúp thêm giá trị vào danh sách.
• Phương thức get_node_val giúp lấy giá trị của nút hiện tại trong danh sách liên kết.
• Phương thức check_cycle giúp tìm xem head và rear có giống nhau không, điều đó có nghĩa là sẽ có chu trình.
• Trả về True hoặc False tùy thuộc vào sự hiện diện hoặc vắng mặt của chu trình.
• Một instance của LinkedList_structure đượ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 trên danh sách liên kết này.
• Kết quả được hiển thị trên console.