Rebrained!

Mth to last – a recursive approach

A collegue of mine was pondering the mthToLast problem for a LinkedList I’d blogged about previously and sent me the following IM message:

just a guess - but can you use  recursion to solve your link list m problem?
a method to track through the list which calls itself,
then when you get to the end start incrementing a counter,
and when it equals M return the value?

I think this is what he meant – it seems to work. Not as scalable as the trailing pointer approach in the previous post, but an interesting excerise in recursion. You find the size at the end, and return it all the way back. The code is a little messy with the 1 element case…anyone have a neater implementation?

class Element:
    def __init__(self,value,next=None):
        self.value=value
        self.next=next

def findMToLast(element,m,counter=1):
        """
        >>> e1=Element(1)
        >>> e2=Element(2)
        >>> e3=Element(3)
        >>> e4=Element(4)
        >>> e1.next=e2
        >>> e2.next=e3
        >>> e3.next=e4
        >>> findMToLast(e1,1).value
        4
        >>> findMToLast(e1,2).value
        3
        >>> findMToLast(e1,3).value
        2
        >>> findMToLast(e1,4).value
        1
        """
        if element.next==None:
            if m==1: mtolast=element
            else: mtolast=None
            if counter ==1: return mtolast
            return (counter,mtolast)
        (size,mtolast)=findMToLast(element.next,m,counter+1)
        if size-counter+1==m: mtolast=element
        if counter==1: return mtolast
        return (size,mtolast)

if __name__ == "__main__":
    import doctest
    doctest.testmod()