ตรวจสอบว่ามีการจัดเรียงรายการที่เชื่อมโยง (Iterative และ Recursive) ใน Python . หรือไม่

สมมติว่าเรามีรายการเชื่อมโยง เราต้องกำหนดสองฟังก์ชันเพื่อตรวจสอบว่ารายการที่เชื่อมโยงนั้นถูกจัดเรียงตามลำดับที่ไม่เพิ่มขึ้นหรือไม่ วิธีการหนึ่งจะทำงานในลักษณะวนซ้ำและอีกวิธีหนึ่งเป็นแบบเรียกซ้ำ

ดังนั้น หากอินพุตเป็น L =[15, 13, 8, 6, 4, 2] ผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน Solv_iter() นี้จะต้องใช้หัว
• ถ้า head เป็น null แล้ว
  • คืนค่า True
• ในขณะที่หัวถัดไปไม่เป็นค่าว่าง ให้ทำ
  • ปัจจุบัน :=หัว
  • ถ้าค่าของกระแส <=ค่าของ (ถัดไปของกระแส) แล้ว
    • คืนค่าเท็จ
  • หัว :=ข้างหัว
• คืนค่า True
• กำหนดฟังก์ชัน Solv_rec() นี้จะต้องใช้หัว
• ถ้า head เป็น null หรือ ถัดไป ของ head เป็น null แล้ว
  • คืนค่า True
• คืนค่า จริง เมื่อ (val of head> ค่าของ (ถัดจาก head) ไม่ใช่ 0 และ Solve_rec(next of head) เป็นจริง) มิฉะนั้น เท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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