Python; Linked list and traversing!

Question

Hi! Starting some programming with python at school now, and I don't know how to proceed with this problem. Any thoughts?

Input consists of integer separated by line breaks. Your program should submit them in a linked list, traverse the linked list and print the highest number.

Something to take the first number, and do an action which says "if the next number is bigger, take that one, else, keep the current number, and head down the list and repeat"

Then when it gets to the end of the list, it prints the value it has.

from sys import stdin

class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt 
        self.neste = None 

def spor(kubbe):
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    for linje in stdin:
        forrige_siste = siste
        siste = Kubbe(int(linje))
        if forste == None:
            forste = siste
        else:
            forrige_siste.neste = siste

# Calls the solution function and prints the result
print spor(forste)

Input: example

54
37
100
123
1
54

Required output

123

Answer 1

There is a builtin function in Python called reduce, which traverses a list and "compresses" it with a given function. That is, if you have a list of five elements [a,b,c,d,e] and a function f, it will effectively do

temp = f(a,b)
temp = f( temp, c )
...

You should be able to use this to write a very neat solution.

If you want to be less abstract, you will need to iterate over each element of the list in turn, storing the greatest number so far in a variable. Change the variable only if the element you have reached is greater than the value of said variable.

Answer 2

"Linked lists" are rarely used in Python -- normally, one uses just list, the Python built-in list, which is actually more of a "dynamic vector". So, it's peculiar to see a linked list specified as part of the exercise's constraints.

But the main point is, the code you're showing is already creating a linked list -- the head is at forste, and, for each node, the next-node pointer at .neste, the payload at .vekt. So, presumably, that's not what you're asking about, no matter the text of your question.

The simple way to loop through your linked list once you have fully constructed it (i.e., at the end of the current code for spor) is

current = forste
while current is not None:
   ...process current.vekt...
   current = current.neste

In your case, the logic for the "process" part is of course, as your Q's text already says:

   if current.vekt > themax:
       themax = current.vekt

The only subtlety is, you need to initially set themax, before this while loop to "the lowest possible number"; in recent versions of Python, "minus infinity" is reliably recorded and compared (though only as a float, it still compares correctly to ints), so

themax = float('-inf')

would work. More elegant might be to initially set the maximum to the first payload, avoiding messing with infinity.

Answer 3

This seems to work with your input (works in both python 2 and 3). Notice how max works with duck typing of Python!

This version works with Python3 also from file.

import sys
class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt 
        self.neste = None 

def spor():
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    while True:
        linje = sys.stdin.readline().rstrip()
        if not linje:
            break

        forrige_siste, siste = siste, Kubbe(int(linje))
        if forste is None:
            forste = siste
        else:
            forrige_siste.neste = siste
    return forste

def traverse(linkedlist):
    while linkedlist is not None:
        yield linkedlist.vekt
        linkedlist=linkedlist.neste

# Calls the solution function and prints the result
linkedlist=spor()

for item in traverse(linkedlist):
    print(item)

# use builtin max:
print('Maximum is %i' % max(traverse(linkedlist)))
# if not allowed:
m = linkedlist.vekt
for item in traverse(linkedlist.neste):
       if item > m:  m = item 
print(m)

Answer 4

Here's an answer based on your own code and language. Sorry if the new variable and function names do not translate well, as I don't speak Norwegian (Google Language Tools is my friend).

Comment: Like airplane Air Traffic Control the default language of most international programming forums such as StackOverflow is English. If you use it, you are likely to get quicker, better, and more answers -- and it probably makes the question and related answers useful to the largest number of other folks. Just my 2 øre... ;-)

from sys import stdin

class Kubbe:
    vekt = None
    neste = None
    def __init__(self, vekt):
        self.vekt = vekt
        self.neste = None

def spor():
    # WRITE YOUR CODE HERE
    # Creates linked list
    forste = None
    siste = None
    while True:
        try:
            linje = raw_input()
        except EOFError:
            break
        forrige_siste = siste
        siste = Kubbe(int(linje))
        if forste == None:
            forste = siste
        else:
            forrige_siste.neste = siste
    return forste

def finne_maksimal(lenketliste):
    storste = None
    if lenketliste is not None:
        storste = lenketliste.vekt
        gjeldende = lenketliste.neste
        while gjeldende is not None:
            if gjeldende.vekt > storste:
                storste = gjeldende.vekt
            gjeldende = gjeldende.neste
    return storste

lenketliste = spor()
storste = finne_maksimal(lenketliste)
if lenketliste is None:
    print "tom liste"
else:
    print "storste er", storste