Chương trình kiểm tra các phần tử danh sách liên kết có tạo thành palindrome không bằng Python

Cho danh sách liên kết, kiểm tra xem các phần tử có tạo thành palindrome hay không. Ví dụ: [5,4,3,4,5] là palindrome, [5,4,3,2,1] không.

Quy trình giải quyết (Đảo nửa đầu danh sách)

1. Dùng con trỏ nhanh fast và chậm slow để tìm giữa danh sách.
2. Trong khi di chuyển, đảo ngược nửa đầu danh sách (lưu trong rev).
3. Sau khi tìm giữa, so sánh nửa sau với nửa đầu đã đảo.
4. Xử lý trường hợp độ dài lẻ/chẵn bằng cờ flag.

Ví dụ mã nguồ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

class Solution:
    def isPalindrome(self, head):
        fast, slow = head, head
        rev = None
        flag = 1
        if not head:
            return True
        while fast and fast.next:
            if not fast.next.next:
                flag = 0
                break
            fast = fast.next.next
            temp = slow
            slow = slow.next
            temp.next = rev
            rev = temp
        fast = slow.next
        slow.next = rev
        if flag:
            slow = slow.next
        while fast and slow:
            if fast.data != slow.data:
                return False
            fast = fast.next
            slow = slow.next
        return True

head = make_list([5, 4, 3, 4, 5])
ob1 = Solution()
print(ob1.isPalindrome(head))  # Output: True

Đầu vào

[5, 4, 3, 4, 5]

Đầu ra

True