লিংকড লিস্ট আইটেম চেক করার প্রোগ্রাম প্যালিনড্রোম তৈরি করছে নাকি পাইথনে নয়

ধরুন আমরা একটি লিঙ্ক তালিকা আছে. তালিকার উপাদানগুলি একটি প্যালিনড্রোম গঠন করছে কিনা তা আমাদের পরীক্ষা করতে হবে। তাই যদি তালিকার উপাদানটি [5,4,3,4,5] এর মতো হয় তবে এটি একটি প্যালিনড্রোম, কিন্তু [5,4,3,2,1] এর মতো একটি তালিকা প্যালিনড্রোম নয়৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• দ্রুত :=হেড, স্লো :=হেড, রেভ :=কিছুই নয় এবং পতাকা :=1
• যদি মাথা খালি থাকে, তাহলে সত্য ফেরত দিন
• যখন দ্রুত এবং পরবর্তী ফাস্ট উপলব্ধ
  • যদি পরবর্তী রোজার পরেরটি পাওয়া যায়, তাহলে পতাকা সেট করুন :=0 এবং লুপ ভাঙুন
  • দ্রুত :=পরের ফাস্টের পরবর্তী
  • temp :=slow, slow :=slow এর পরের
  • temp :=rev, এবং rev :=temp
• দ্রুত :=ধীরের পরের, এবং ধীরের পরের :=রেভ
• যদি পতাকা সেট করা থাকে, তাহলে 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