สมมติว่าเรามีรายการเชื่อมโยง เราต้องตรวจสอบว่าองค์ประกอบรายการกำลังก่อตัวเป็นพาลินโดรมหรือไม่ ดังนั้นหากองค์ประกอบรายการเป็นเหมือน [5,4,3,4,5] นี่คือพาลินโดรม แต่รายการอย่าง [5,4,3,2,1] ไม่ใช่พาลินโดรม
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เร็ว :=หัว, ช้า :=หัว, รอบ :=ไม่มีและตั้งค่าสถานะ:=1
- ถ้า head ว่าง ก็คืนค่า true
- ในขณะที่ fast และ next of fast พร้อมใช้งาน
- หากมีรายการถัดไปของ fast ถัดไป ให้ตั้งค่าแฟล็ก :=0 และทำลายลูป
- เร็ว :=ถัดไปจากถัดไปอย่างรวดเร็ว
- temp :=ช้า ช้า :=ถัดจากช้า
- ถัดไปของ temp :=rev และ rev :=temp
- เร็ว :=ถัดไปจากช้า และถัดไปของช้า :=rev
- หากตั้งค่าสถานะไว้ ให้ช้า :=ถัดจากช้า
- ทั้งที่เร็วและช้าไม่ใช่ไม่มี
- ถ้าค่า fast ไม่เท่ากับค่า slow ให้คืนค่าเท็จ
- เร็ว :=ถัดจากเร็วและช้า :=ถัดจากช้า
- คืนค่าจริง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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))
อินพุต
[5,4,3,4,5]
ผลลัพธ์
True
