Python中檢查連結串列是否已排序（迭代和遞迴）

假設我們有一個連結串列，我們需要定義兩個函式來檢查該連結串列是否按非遞增順序排序。其中一個方法將以迭代方式工作，另一個方法將以遞迴方式工作。

因此，如果輸入類似於 L = [15, 13, 8, 6, 4, 2]，則輸出將為 True。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 solve_iter()。這將接收頭節點。
  • 如果頭節點為空，則
    • 返回 True
  • 當頭節點的下一個節點不為空時，執行以下操作：
    • current := head
    • 如果 current 的值 <= current 的下一個節點的值，則
      • 返回 False
    • head := head 的下一個節點
  • 返回 True
  • 定義一個函式 solve_rec()。這將接收頭節點。
  • 如果頭節點為空或頭節點的下一個節點為空，則
    • 返回 True
  • 如果(head的值 > head的下一個節點的值)為真 且 solve_rec(head的下一個節點) 為真，則返回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

更新於：2021年1月19日

463 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告