Giả sử chúng ta có một danh sách liên kết. Chúng ta phải kiểm tra xem các phần tử trong danh sách có đang hình thành apalindrome hay không. Vì vậy, nếu phần tử danh sách giống như [1,2,3,2,1], thì đây là một palindrome.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
fast:=head, slow:=head, rev:=Không có và cờ:=1
-
nếu phần đầu trống, thì trả về true
-
trong khi nhanh chóng và nhanh chóng tiếp theo có sẵn
-
nếu tiếp theo của fast tiếp theo có sẵn, thì hãy đặt cờ:=0 và ngắt vòng lặp
-
fast:=next of the next of fast
-
temp:=slow, slow:=tiếp theo của chậm
-
tiếp theo của temp:=rev và rev:=temp
-
-
fast:=next of slow, and next of slow:=rev
-
nếu cờ được đặt, thì chậm:=tiếp theo của chậm
-
trong khi nhanh và chậm không phải là Không có,
-
nếu giá trị của fast không giống với giá trị của slow, thì trả về false
-
fast:=next of fast, and slow:=next of slow
-
-
trả về true
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class ListNode:def __init __ (self, data, next =None):self.data =data self.next =nextdef make_list (các phần tử):head =ListNode (các phần tử [0]) cho phần tử trong các phần tử [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 flag =1 if not head:trả về True trong khi nhanh và nhanh. tiếp theo:nếu không nhanh.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 trong khi fast and slow:if fast.data! =slow.data:return Sai nhanh =fast.next slow =slow.next return Truehead =make_list ([1,2,3,2,1]) ob1 =Solution () print (ob1.isPalindrome (head))Đầu vào
[1,2,3,2,1]Đầu ra
Đúng