मान लीजिए हमारे पास एक लिंक्ड लिस्ट है हमें दो फ़ंक्शन परिभाषित करने हैं जो जांचते हैं कि लिंक्ड लिस्ट गैर-बढ़ते क्रम में सॉर्टेड है या नहीं। एक विधि इटरेटिव तरीके से काम करेगी और दूसरी रिकर्सिव तरीके से।
तो, यदि इनपुट L = [15, 13, 8, 6, 4, 2] है, तो आउटपुट True होगा।
हल करने के चरण
- solve_iter() फ़ंक्शन परिभाषित करें। यह head लेगा
- यदि head null है, तो:
- True लौटाएं
- जब तक head का next null नहीं है, तब तक:
- current := head
- यदि current का मान <= (current के next) का मान, तो:
- False लौटाएं
- head := head का next
- True लौटाएं
- solve_rec() फ़ंक्शन परिभाषित करें। यह head लेगा
- यदि head null है या head का next null है, तो:
- True लौटाएं
- true लौटाएं जब (head का मान > head के next का मान 0 नहीं है और solve_rec(head का next) true है) अन्यथा 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
