リンクリストがPythonでソート（反復および再帰）されているかどうかを確認します

リンクリストがあるとすると、リンクリストが昇順ではない順序で並べ替えられているかどうかを確認するために2つの関数を定義する必要があります。 1つの方法は反復的に機能し、もう1つは再帰的に機能します。

したがって、入力がL =[15、13、8、6、4、2]の場合、出力はTrueになります。

これを解決するには、次の手順に従います-

• 関数solve_iter（）を定義します。これは頭​​を悩ます
• ヘッドがnullの場合、
  • Trueを返す
• 次の頭がnullでない場合は、
  • 現在：=頭
  • 現在の値<=（現在の次の）の値の場合、
    • Falseを返す
  • 頭：=頭の次
• Trueを返す
• 関数solve_rec（）を定義します。これは頭​​を悩ます
• ヘッドがヌルまたはヘッドの次がヌルの場合、
  • Trueを返す
• （頭の値>（頭の次）の値が0でなく、solve_rec（頭の次）が真の場合は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