reverse_linked_list.py

"""
>>> gen(10)
[0, [1, [2, [3, [4, [5, [6, [7, [8, [9, []]]]]]]]]]]
>>> rev_by_recur(gen(10))
[9, [8, [7, [6, [5, [4, [3, [2, [1, [0, []]]]]]]]]]]
>>> rev_by_loop(gen(10))
[9, [8, [7, [6, [5, [4, [3, [2, [1, [0, []]]]]]]]]]]
"""

def gen(n):
    L = S = []
    for i in range(10):
        S.extend([i, []])
        S = S[-1]
    return L

def rev_by_recur(head) -> "new head":
    def rechain(parent, me) -> "new head":
        if me:
            child, me[-1] = me[-1], parent
            return rechain(me, child)
        else:
            return parent
    return rechain([], head)

def rev_by_loop(head) -> "new head":
    parent, me = [], head
    while me:
        child, me[-1] = me[-1], parent
        parent, me = me, child
    return parent