পাইথনে লিঙ্ক করা তালিকাটি সাজানো (পুনরাবৃত্ত এবং পুনরাবৃত্তিমূলক) কিনা তা পরীক্ষা করুন

ধরুন আমাদের একটি লিঙ্কযুক্ত তালিকা আছে আমাদের দুটি ফাংশন সংজ্ঞায়িত করতে হবে যাতে লিঙ্ক করা তালিকাটি অ-ক্রমবর্ধমান ক্রমে বাছাই করা হয় কিনা। একটি পদ্ধতি পুনরাবৃত্তিমূলক পদ্ধতিতে এবং অন্যটি পুনরাবৃত্তিমূলক পদ্ধতিতে কাজ করবে।

সুতরাং, যদি ইনপুট L =[15, 13, 8, 6, 4, 2] এর মত হয়, তাহলে আউটপুট হবে True।

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

• একটি ফাংশন সংজ্ঞায়িত করুন solve_iter()। এটি মাথা নেবে
• হেড যদি শূন্য হয়, তাহলে
  • সত্য ফেরান
• যদিও হেডের পাশে শূন্য না হয়, ডু
  • বর্তমান :=মাথা
  • যদি বর্তমানের মান <=(কারেন্টের পরবর্তী) মান হয়, তাহলে
    • মিথ্যে ফেরত দিন
  • মাথা :=মাথার পাশে
• সত্য ফেরান
• একটি ফাংশন সংজ্ঞায়িত করুন solve_rec()। এটি মাথা নেবে
• যদি হেড নাল হয় বা হেডের পাশে নাল হয়, তাহলে
  • সত্য ফেরান
• সত্য ফেরত দিন যখন (হেডের মান> (হেডের পরের) এর মান 0 না হয় এবং সমাধান_রেক (হেডের পরের) সত্য হয়) অন্যথায় মিথ্যা হয়

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

class ListNode:
   def __init__(self, data, next = None):
      self.val = 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
def solve_iter(head):
   if head == None:
      return True
   while head.next != None:
      current = head
      if current.val <= current.next.val:
         return False
      head = head.next
   return True
def solve_rec(head):
   if head == None or head.next == None:
      return True
   return head.val > head.next.val and solve_rec(head.next)
L = make_list([15, 13, 8, 6, 4, 2])
print(solve_iter(L))
print(solve_rec(L))

ইনপুট

[15, 13, 8, 6, 4, 2]

আউটপুট

True
True