สมมติว่าเรามีรายการที่เชื่อมโยง เราต้องตรวจสอบว่าองค์ประกอบรายการกำลังก่อตัวเป็น apalindrome หรือไม่ ดังนั้นหากองค์ประกอบรายการเป็นเหมือน [1,2,3,2,1] นี่คือพาลินโดรม
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เร็ว :=หัว, ช้า :=หัว, รอบ :=ไม่มีและตั้งค่าสถานะ:=1
-
หากส่วนหัวว่างเปล่าให้คืนค่าเป็น จริง
-
ในขณะที่ fast และ next of fast สามารถใช้ได้
-
ถ้า next of next of fast ใช้ได้ ให้ตั้งค่า flag :=0 และทำลาย loop
-
เร็ว :=ถัดไปของเร็ว
-
temp :=ช้า ช้า :=ถัดจากช้า
-
ถัดไปของ temp :=rev และ rev :=temp
-
-
เร็ว :=ถัดไปจากช้า และถัดไปของช้า :=rev
-
หากตั้งค่าสถานะไว้ช้า :=ถัดไปช้า
-
ในขณะที่เร็วและช้าไม่ใช่ไม่มี
-
ถ้าค่า fast ไม่เหมือนค่า slow ก็คืนค่า false
-
เร็ว :=ถัดจากเร็ว และช้า :=ถัดจากช้า
-
-
คืนความจริง
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
คลาส ListNode:def __init__(self, data, next =None):self.data =data self.next =nextdef make_list(elements):head =ListNode(elements[0]) สำหรับองค์ประกอบในองค์ประกอบ[1:] :ptr =head while ptr.next:ptr =ptr.next ptr.next =ListNode(element) return headclass Solution(object):def isPalindrome(self, head):fast,slow =head,head rev =None แฟล็ก =1 ถ้าไม่ใช่ head:คืนค่า True ในขณะที่ fast และ fast.next:if not fast.next.next:flag =0 break fast =fast.next.next temp =slow slow =slow.next temp.next =rev rev =temp #print (fast.val) 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 Truehead =make_list([1,2,3,2,1])ob1 =Solution()print(ob1.isPalindrome(head))อินพุต
[1,2,3,2,1]ผลลัพธ์
จริง
