Inplace linked list re-arrangement

inplace_rearrange.py

'''
Problem statement:

you have input list: L0 -> L1 -> L2 -> ..... -> Ln -> Ln-1
output: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ....

'''

class Node(object):
    def __init__(self, val, _next=None):
        self.val = val
        self.next = _next
    
    def __repr__(self):
        return str(self.val)

    #def __cmp__(self, other):
    #    print "..."
    #    return self.val == other.val


class RL(object):
    def __init__(self):
        self.head = None
        self.tail = None
        
    def add(self, val):
        nn = Node(val)
        if self.head is None:
            self.head = nn
            self.tail = nn
        else:
            # inserting at the end
            node = self.head
            while node.next:
                node = node.next
            node.next = nn
            self.tail = nn

    def __str__(self):
        return self.print_ll()

    def __repr__(self):
        return self.print_ll()

    def print_ll(self):
        ps = ''
        node = self.head
        while node:
            ps += '%s -> ' % node.val
            node = node.next
        return ps.rstrip('-> ')

    def _split_end_node(self):
        node = self.head
        while node.next:
            prev = node
            node = node.next
        prev.next = None
        self.tail = prev
        return node

    def inplace_arrangement(self):
        '''
        Arranging the elements in place
        L0 -> L1 -> L2 -> L3 -> L4 -> L5
        L0 -> L5 -> L1 -> L4 -> L2 -> L3
        '''
        start = self.head
        tmp = start.next
        end = self._split_end_node()
        
        while tmp.next and tmp != end:
            start.next = end
            end.next = tmp
            start = tmp
            tmp = tmp.next
            end = self._split_end_node()
   
        start.next = tmp
        if tmp != end:
            tmp.next = end
        

if __name__ == '__main__':
    m = RL()
    m.add(5)
    m.add(4)
    m.add(2)
    m.add(10)
    m.add(12)
    m.add(11)
    m.add(20)
    m.add(1)
    m.add(1)
    m.add(1)
    m.add(1)

    print "Initial List:"
    print m
    m.inplace_arrangement()
    print "Output:"
    print m