Python에서 연결 목록이 정렬되어 있는지 확인(반복 및 재귀)

연결 목록이 있다고 가정해 보겠습니다. 연결 목록이 오름차순으로 정렬되어 있는지 여부를 확인하기 위해 두 개의 함수를 정의해야 합니다. 방법 중 하나는 반복적 방식으로 작동하고 다른 하나는 재귀적 방식으로 작동합니다.

따라서 입력이 L =[15, 13, 8, 6, 4, 2]와 같으면 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• solve_iter() 함수를 정의합니다. 이것은 머리가 걸릴 것입니다
• head가 null이면
  • 참 반환
• head의 다음이 null이 아닌 동안 do
  • 현재 :=머리
  • 현재 값 <=(현재의 다음 값)인 경우
    • 거짓을 반환
  • head :=머리 옆
• 참 반환
• solve_rec() 함수를 정의합니다. 이것은 머리가 걸릴 것입니다
• head가 null이거나 head의 다음이 null이면
  • 참 반환
• (머리의 val> (머리의 다음) 값이 0이 아니고 solve_rec(머리의 다음)이 참인 경우) 그렇지 않으면 거짓을 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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