जांचें कि क्या लिंक की गई सूची को पायथन में क्रमबद्ध किया गया है (पुनरावर्ती और पुनरावर्ती)

मान लीजिए कि हमारे पास एक लिंक्ड सूची है, तो हमें यह जांचने के लिए दो कार्यों को परिभाषित करना होगा कि लिंक की गई सूची को गैर-बढ़ते क्रम में क्रमबद्ध किया गया है या नहीं। एक विधि पुनरावर्ती तरीके से काम करेगी और दूसरी पुनरावर्ती तरीके से।

इसलिए, यदि इनपुट L =[15, 13, 8, 6, 4, 2] जैसा है, तो आउटपुट सही होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन को परिभाषित करें 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