how to get min or max value from a linked list?

Question

I am trying to define a function that can get min value from a linked list of ints.

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

Function list_to_ll convert a normal list to linked list:

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)

For example:

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

But my function gives me:

RuntimeError: maximum recursion depth exceeded in comparison

Please help. Actual codes would be really appreciated.

Answer 1

I have done this in python. Here fist we created a circular link list and then we print minNode() value and maxNode() value.

#Represents the node of list.    
class Node:    
    def __init__(self,data):    
    self.data = data;    
        self.next = None;    

class CreateList:    
    #Declaring head and tail pointer as null.    
    def __init__(self):    
        self.head = Node(None);    
        self.tail = Node(None);    
        self.head.next = self.tail;    
        self.tail.next = self.head;  



#This function will add the new node at the end of the list.    
def add(self,data):    
    newNode = Node(data);    
    #Checks if the list is empty.    
    if self.head.data is None:    
        #If list is empty, both head and tail would point to new node.    
        self.head = newNode;    
        self.tail = newNode;    
        newNode.next = self.head;    
    else:    
        #tail will point to new node.    
        self.tail.next = newNode;    
        #New node will become new tail.    
        self.tail = newNode;    
        #Since, it is circular linked list tail will point to head.    
        self.tail.next = self.head;    

#Finds out the minimum value node in the list    
def minNode(self):    
    current = self.head;    
    #Initializing min to initial node data    
    minimum = self.head.data;    
    if(self.head == None):    
        print("List is empty");    
    else:    
        while(True):    
            #If current node's data is smaller than min    
            #Then replace value of min with current node's data    
            if(minimum > current.data):    
                minimum = current.data;    
            current= current.next;    
            if(current == self.head):    
                break;    
    print("Minimum value node in the list: "+ str(minimum));    

#Finds out the maximum value node in the list    
def maxNode(self):    
    current = self.head;    
    #Initializing max to initial node data    
    maximum = self.head.data;    
    if(self.head == None):    
        print("List is empty");    
    else:    
     while(True):    
            #If current node's data is greater than max    
            #Then replace value of max with current node's data    
            if(maximum < current.data):    
                maximum = current.data;    
            current= current.next;    
            if(current == self.head):    
                break;    
    print("Maximum value node in the list: "+ str(maximum));    

class CircularLinkedList:    
    cl = CreateList();    
    #Adds data to the list    
    cl.add(5);    
    cl.add(20);    
    cl.add(10);    
    cl.add(1);    
    #Prints the minimum value node in the list    
    cl.minNode();    
    #Prints the maximum value node in the list    
    cl.maxNode();

Source:coderforevers.com

Answer 2

Your get_min function contains the following mistakes:

• the base case should be if ll.next == None and not if ll == None. Indeed the minimum of the empty list is not well-defined. But if ll.next is None it means that your list only contains one item. In that case the minimum of the list is the item itself, i.e. ll.value

• when the list has more than one element, the minimum of the list can be obtained by comparing the first element of the list (ll.value) to the minimum of the remaining list starting at ll.next (the tail of the list).

• finally it is a better practice to use the is operator to test if a Python variable is None.

A working code could be the following:

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

If you can use the min function to compare two numbers, a more concise version is:

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

Finally, you could raise an exception when the list is empty to warn the user of the function that he is using it in a non-applicable case:

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 3

Implement __iter__ for your data structure so you can iterate over it. Then you can use the regular min() and max() functions (as well as for loops, the any() and all() functions, map() and list comprehensions... etc.).

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