Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> Python

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

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

इसलिए, यदि इनपुट 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

  1. सी ++ में लिंक्ड लिस्ट के वैकल्पिक विभाजन के लिए रिकर्सिव दृष्टिकोण

    इनपुट के रूप में सिंगल लिंक्ड लिस्ट को देखते हुए। लक्ष्य सूची को दो एकल लिंक की गई सूचियों में विभाजित करना है जिनमें मूल सूची के वैकल्पिक नोड हैं। यदि इनपुट सूची में नोड्स a → b → c → d → e → f हैं तो विभाजन के बाद, दो उप-सूचियाँ a → c → e और b → d → f होंगी। हम दो पॉइंटर्स N1 और N2 लेंगे, एक मूल

  1. C++ में रिकर्सिव इंसर्शन और ट्रैवर्सल लिंक्ड लिस्ट

    हमें पूर्णांक मान दिए गए हैं जिनका उपयोग एक लिंक्ड सूची बनाने के लिए किया जाएगा। कार्य पहले एक पुनरावर्ती दृष्टिकोण का उपयोग करके एक एकल लिंक की गई सूची को सम्मिलित करना और फिर पार करना है। अंत में नोड्स का पुनरावर्ती जोड़ अगर सिर खाली है → सिर में नोड जोड़ें और सिर में जोड़ें(सिर → अगला) नो

  1. सी ++ में क्रमबद्ध और घुमाए गए लिंक्ड सूची में घूर्णन की गणना करें

    हमें एक लिंक्ड लिस्ट दी गई है। सूची को पहले क्रमबद्ध किया जाता है और फिर K संख्या के नोड्स द्वारा घुमाया जाता है। लक्ष्य K का मान ज्ञात करना है। यदि हमें इनपुट के रूप में लिंक की गई सूची नीचे दी गई है, जिसे K नोड्स की संख्या द्वारा घुमाया जाता है - तब मूल अवश्य रहा होगा - और हम देख सकते हैं K