Chương trình Python chuyển đổi Danh sách liên kết đơn thành Danh sách liên kết vòng

Khi cần chuyển đổi một danh sách liên kết đơn (singly linked list) thành danh sách liên kết vòng (circular linked list), một phương thức tên convert_to_circular_list được định nghĩa để đảm bảo phần tử cuối cùng trỏ về phần tử đầu tiên, làm cho nó trở thành vòng.

Ví dụ

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

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

    def add_elements(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 convert_to_circular_list(my_list):
    if my_list.last_node:
        my_list.last_node.next = my_list.head

def last_node_points(my_list):
    last = my_list.last_node
    if last is None:
        print('Danh sách rỗng...')
        return
    if last.next is None:
        print('Nút cuối trỏ đến None...')
    else:
        print('Nút cuối trỏ đến phần tử có giá trị {}...'.format(last.next.data))

my_instance = LinkedList_struct()
my_input = input('Nhập các phần tử của danh sách liên kết: ').split()
for data in my_input:
    my_instance.add_elements(int(data))

last_node_points(my_instance)
print('Đang chuyển đổi danh sách liên kết thành danh sách liên kết vòng...')
convert_to_circular_list(my_instance)
last_node_points(my_instance)

Kết quả

Nhập các phần tử của danh sách liên kết: 56 32 11 45 90 87
Nút cuối trỏ đến None...
Đang chuyển đổi danh sách liên kết thành danh sách liên kết vòng...
Nút cuối trỏ đến phần tử có giá trị 56...

Giải thích

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

• Lớp LinkedList_struct với các thuộc tính cần thiết được tạo.

• Phương thức __init__ khởi tạo nút đầu (head) và nút cuối (last_node) là None.

• Phương thức add_elements thêm phần tử vào danh sách liên kết.

• Phương thức convert_to_circular_list trỏ nút cuối về nút đầu, tạo thành vòng.

• Phương thức last_node_points kiểm tra xem danh sách rỗng, nút cuối trỏ None hay trỏ đến nút cụ thể.

• Một đối tượng của lớp LinkedList_struct được tạo.

• Nhập các phần tử của danh sách liên kết từ người dùng.

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

• Gọi phương thức last_node_points trên danh sách này.

• Hiển thị kết quả ra bảng điều khiển.