如何從鏈表中獲取最小值或最大值？

Question

我想定義一個函數，可以從一個int的鏈表中獲取最小值。

Given Function(not allowed to be modified): 
class LN: 
    def __init__(self,value,next=None): 
     self.value = value 
     self.next = next 

    def list_to_ll(l): 
     if l == []: 
      return None 
     front = rear = LN(l[0]) 
     for v in l[1:]: 
      rear.next = LN(v) 
      rear = rear.next 
     return front 

功能list_to_ll正常列表轉換爲鏈表：

A recursive function I am trying to define: 
def get_min(ll): 
    if ll == None: 
     return None 
    else: 
     if ll.value < ll.next.value: 
      return ll.value 
     return get_min(ll.next) 

例如：

get_min(list_to_ll([7, 3, 5, 2, 0]))--> 0 

但我的功能給我：

RuntimeError: maximum recursion depth exceeded in comparison 

請幫助。實際的代碼將非常感激。

Answer 1

你get_min功能包含以下錯誤：

• 基本情況應該是if ll.next == None而不是if ll == None。事實上，空單的最低限度並不明確。但是，如果ll.next是None這意味着您的列表只包含一個項目。在這種情況下，列表的最小是物品本身，即ll.value

• 當列表具有多於一個元素，該列表的最小可通過第一元件比較所述列表的獲得（ll.value）到剩餘列表的最小值從ll.next（列表的尾部）開始。

• 最後，使用is運算符來測試Python變量是否爲None是一種更好的做法。

的工作代碼可能是以下幾點：

def get_min(ll): 
    if ll.next is None: 
     return ll.value 
    else: 
     tail_min = get_min(ll.next) 
     if ll.value < tail_min: 
      return ll.value 
     else: 
      return tail_min 

如果你可以使用min函數來比較兩個數字，一個更簡潔的版本是：

def get_min(ll): 
    if ll.next is None: 
     return ll.value 
    else: 
     return min(ll.value, get_min(ll.next)) 

最後，當列表爲空時可能會引發異常，以警告用戶在非適用情況下使用該功能的用戶：

def get_min(ll): 
    if ll is None: 
     raise ValueError("Cannot compute the minimum of the empty list.") 
    elif ll.next is None: 
     return ll.value 
    else: 
     return min(ll.value, get_min(ll.next)) 

Answer 2

爲您的數據結構實施__iter__，以便您可以遍歷它。然後，您可以使用常規功能min()和max()功能（以及for循環，any()和all()功能，map()和列表解析等）。

def __iter__(self): 
    ptr = self 
    while ptr is not None: 
     yield ptr.value 
     ptr = ptr.next