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 palindrome hay không. Vì vậy, nếu phần tử danh sách giống như [5,4,3,4,5], thì đây là một palindrome, nhưng một danh sách như [5,4,3,2,1] không phải 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à tiếp theo là nhanh chóng có sẵn
- nếu có sẵn phần tiếp theo của fast, thì hãy đặt cờ:=0 và ngắt vòng lặp
- fast:=next of the next of fast
- temp:=chậm, chậm:=tiếp theo của chậm
- tiếp theo của temp:=rev và rev:=temp
- fast:=next of slow và next of slow:=rev
- nếu cờ được đặt, thì làm 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
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[5,4,3,4,5]
Đầu ra
True