โปรแกรมตรวจสอบลิงก์ลิสต์เป็นพาลินโดรมหรือไม่ใน Python

สมมติว่าเรามีลิงก์ลิสต์ เราต้องตรวจสอบว่าสมาชิกในลิสต์เป็นพาลินโดรมหรือไม่ เช่น [5,4,3,4,5] เป็นพาลินโดรม แต่ [5,4,3,2,1] ไม่ใช่

ขั้นตอนการแก้ปัญหา (Two Pointers + Reverse Half)

1. fast = head, slow = head, rev = None, flag = 1
2. ถ้า head ว่าง คืนค่า True
3. วนลูป while fast และ fast.next:
   • ถ้า fast.next.next ไม่มี: flag = 0, break
   • fast = fast.next.next
   • temp = slow, slow = slow.next
   • temp.next = rev, rev = temp (กลับครึ่งหน้า)
4. fast = slow.next, slow.next = rev
5. ถ้า flag ตั้งไว้: slow = slow.next
6. วนลูป while fast และ slow:
   • ถ้า fast.data != slow.data: คืนค่า False
   • fast = fast.next, slow = slow.next
7. คืนค่า True

ตัวอย่างโค้ด 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([5,4,3,4,5])
ob1 = Solution()
print(ob1.isPalindrome(head))  # Output: True

อินพุต / เอาต์พุต

Input: [5,4,3,4,5]

Output: True