Kiểm tra xem danh sách được liên kết có được sắp xếp (Lặp lại và Đệ quy) trong Python hay không

Giả sử chúng ta có một danh sách liên kết, chúng ta phải xác định hai hàm để kiểm tra xem danh sách liên kết có được sắp xếp theo thứ tự không tăng dần hay không. Một trong các phương thức sẽ hoạt động theo cách lặp lại và một phương thức khác theo cách đệ quy.

Vì vậy, nếu đầu vào là L =[15, 13, 8, 6, 4, 2], thì đầu ra sẽ là True.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Định nghĩa một hàm giải quyết_iter (). Điều này sẽ mất đầu
• nếu head rỗng, thì
  • trả về True
• trong khi phần tiếp theo của phần đầu không rỗng, hãy thực hiện
  • hiện tại:=head
  • nếu giá trị của hiện tại <=giá trị của (tiếp theo của hiện tại), thì
    • trả về Sai
  • head:=tiếp theo của head
• trả về True
• Định nghĩa một hàm giải quyết_rec (). Điều này sẽ mất đầu
• nếu phần đầu là rỗng hoặc phần tiếp theo của phần đầu là rỗng, thì
  • trả về True
• trả về true khi (val of head> value of (next of head) không phải là 0 và giải quyết_rec (next of head) là true) nếu không thì false

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[15, 13, 8, 6, 4, 2]

Đầu ra

True
True