เช็คลิงก์ลิสต์แบบพาลินโดรมใน Python

ภาพรวมปัญหา

ให้ลิงก์ลิสต์ (linked list) ต้องการตรวจสอบว่าลำดับของข้อมูลในลิสต์เป็นพาลินโดรม (palindrome) หรือไม่ คืออ่านจากหน้าไปหลังและหลังมาหน้าได้เหมือนกัน

ตัวอย่าง: [1,2,3,2,1] เป็นพาลินโดรม

ขั้นตอนการแก้ปัญหา

1. ใช้ pointer 2 ตัว: fast (กระโดด 2 ขั้น) และ slow (เดิน 1 ขั้น) พร้อมกันสร้างลิสต์ย้อนกลับ (rev) จากครึ่งแรก
2. ถ้า head ว่าง คืน True
3. วนลูปจน fast หรือ fast.next เป็น None:
   • ถ้า fast.next.next ไม่มี ให้ตั้ง flag = 0 แล้ว break (จำนวนคี่)
   • เลื่อน fast 2 ขั้น, slow 1 ขั้น และสร้าง rev ด้วยการกลับ pointer
4. ปรับ pointer สำหรับครึ่งหลัง: fast = slow.next, slow.next = rev
5. ถ้า flag = 1 (จำนวนคู่) ให้เลื่อน slow = slow.next
6. เปรียบเทียบ fast และ slow ทีละโหนด ถ้าค่าไม่เท่ากัน คืน False
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([1, 2, 3, 2, 1])
ob1 = Solution()
print(ob1.isPalindrome(head))

อินพุต

[1,2,3,2,1]

เอาต์พุต

True