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 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告