পাইথনে লিংকড লিস্ট সর্টেড কিনা তা যাচাই করা (ইটেরেটিভ এবং রিকার্সিভ)

মান লিজিয়ে আমাদের একটি লিংকড লিস্ট আছে, আমাদের দুটি ফাংশন সংজ্ঞায়িত করতে হবে যাতে লিংকড লিস্টটি নন-ইনক্রিজিং ক্রমে (non-increasing order) সর্টেড কিনা তা যাচাই করা যায়। একটি মেথড ইটেরেটিভ (iterative) পদ্ধতিতে কাজ করবে আরেকটি রিকার্সিভ (recursive) পদ্ধতিতে।

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

সমাধানের ধাপসমূহ

• solve_iter() ফাংশন সংজ্ঞায়িত করুন। এটি head নেবে
  • যদি head নাল (null) হয়, তবে:
    • True রিটার্ন করুন
  • যখন head-এর নেক্সট নাল নয়, করুন:
    • current := head
    • যদি current-এর ভ্যালু current-এর নেক্সটের ভ্যালু থেকে ছোট বা সমান হয়, তবে:
      • False রিটার্ন করুন
    • head := head-এর নেক্সট
  • True রিটার্ন করুন
• solve_rec() ফাংশন সংজ্ঞায়িত করুন। এটি head নেবে
  • যদি head নাল হয় অথবা head-এর নেক্সট নাল হয়, তবে:
    • True রিটার্ন করুন
  • true রিটার্ন করুন যখন (head-এর ভ্যালু > head-এর নেক্সটের ভ্যালু ০ নয় এবং solve_rec(head.next) সত্য) অন্যথায় false

উদাহরণ

বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন:

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