Chương trình Python kiểm tra Danh sách liên kết đơn có phải Palindrome không

Khi cần kiểm tra xem một danh sách liên kết đơn (singly linked list) có phải là palindrome (đối xứng) hay không, các phương thức thêm phần tử, lấy nút trước và kiểm tra palindrome được định nghĩa.

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 get_previous_node(self, ref_node):
        curr = self.head
        while curr and curr.next != ref_node:
            curr = curr.next
        return curr

def check_palindrome(my_list):
    beg = my_list.head
    end = my_list.last_node
    while beg != end and end.next != beg:
        if beg.data != end.data:
            return False
        beg = beg.next
        end = my_list.get_previous_node(end)
    return True

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

if check_palindrome(my_instance):
    print('Danh sách liên kết có tính đối xứng (palindromic)')
else:
    print('Danh sách liên kết KHÔNG có tính đối xứng')

Kết quả

Nhập các phần tử cho danh sách liên kết: 89 90 78 90 89
Danh sách liên kết có tính đối xứng (palindromic)

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.

• Phương thức get_previous_node lấy nút trước một nút tham chiếu.

• Phương thức check_palindrome so sánh phần tử đầu và cuối, nếu khác nhau thì không phải palindrome.

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

• Nhập các phần tử từ người dùng.

• Thêm các phần tử vào danh sách.

• Gọi check_palindrome trên danh sách này.

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