Как получить минимальное или максимальное значение из связанного списка?

Question

Я пытаюсь определить функцию, которая может получить значение min из связанного списка 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