Danh Sách Liên Kết Palindrome trong Python

Cho một danh sách liên kết đơn. Kiểm tra xem các phần tử của danh sách có tạo thành một palindrome (xâu đối xứng) hay không. Ví dụ: danh sách [1,2,3,2,1] là palindrome.

Thuật toán giải quyết

1. Khởi tạo con trỏ fast và slow đều trỏ về head, rev = None (danh sách đảo ngược), flag = 1.
2. Nếu head rỗng, trả về true.
3. Dùng thuật toán "fast & slow pointer" để tìm giữa danh sách và đồng thời đảo ngược nửa đầu:
   • Trong khi fast và fast.next tồn tại:
     • Nếu fast.next.next không tồn tại (số phần tử chẵn), đặt flag = 0 và thoát vòng lặp.
     • Di chuyển fast = fast.next.next.
     • Đảo ngược liên kết: temp = slow, slow = slow.next, temp.next = rev, rev = temp.
4. Điều chỉnh con trỏ cho nửa sau: fast = slow.next, slow.next = rev.
5. Nếu flag = 1 (số phần tử lẻ), bỏ qua phần tử giữa: slow = slow.next.
6. So sánh hai nửa: duyệt fast và slow, nếu giá trị khác nhau trả về false.
7. Trả về true nếu toàn bộ khớp.

Ví dụ (Python)

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(object):
    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([1, 2, 3, 2, 1])
ob1 = Solution()
print(ob1.isPalindrome(head))

Đầu vào

[1, 2, 3, 2, 1]

Đầu ra

True