โปรแกรม Python ตรวจสอบว่า Singly Linked List เป็น Palindrome หรือไม่

เมื่อต้องการตรวจสอบว่า Singly Linked List เป็น Palindrome (อ่านจากหน้าหลังได้เหมือนกัน) หรือไม่ สามารถเปรียบเทียบโหนดแรกกับโหนดสุดท้าย แล้วเลื่อนเข้ามาเรื่อยๆ

โค้ดตัวอย่าง

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('Enter elements to the linked list: ').split()
for data in my_input:
    my_instance.add_elements(int(data))

if check_palindrome(my_instance):
    print('The linked list is palindromic in nature')
else:
    print('The linked list is not palindromic in nature')

ผลลัพธ์

Enter elements to the linked list: 89 90 78 90 89
The linked list is palindromic in nature

คำอธิบาย

• คลาส Node และ LinkedList_struct เหมือนตัวอย่างก่อนหน้า

• เมธอด get_previous_node: หาโหนดก่อนหน้าของ ref_node โดย traverse จาก head (O(n))

• ฟังก์ชัน check_palindrome: ใช้ two pointers (beg จากหน้า, end จากหลัง) เปรียบเทียบค่า แล้วเลื่อน beg ไปข้างหน้า, end ไปข้างหลัง (ผ่าน get_previous_node)

• เงื่อนไขหยุด: beg != end and end.next != beg ครอบคลุมทั้งกรณีจำนวนโหนดคู่และคี่

ข้อจำกัด: วิธีนี้ใช้เวลา O(n²) เพราะ get_previous_node ใช้ O(n) เรียกซ้ำ n/2 ครั้ง วิธีที่ดีกว่า (O(n) time, O(1) space):

1. หาจุดกลางด้วย slow/fast pointer
2. Reverse ครึ่งหลังของ linked list
3. เปรียบเทียบครึ่งหน้ากับครึ่งหลังที่ reverse แล้ว
4. Reverse กลับคืนเพื่อคืนสภาพเดิม (optional)