#!/usr/bin/env python

class ListNode:
    def __init__(self, value=0, next=None):
        self.val = value
        self.next = next

def create_list(values):
    head = None
    for value in values[::-1]:
        head = ListNode(value,head)
    return head

def create_list2(values):
    head = None
    pre = None
    for i in range(0,len(values),1):
        cur = ListNode(values[i],None)
        if pre is not None:
            pre.next = cur
            pre = cur
        else:
            head = cur
            pre = cur
    return head

def print_list(head):
    val = ""
    cur = head

    while cur is not None:
        val = val + str(cur.val) + '->'
        cur = cur.next
    val = val + 'Null'
    print(val)

def reverse_list(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

def reverse_list2(head):
    pre = None
    cur = head
    next_node = None
    while cur is not None:
        next_node = cur.next
        cur.next = pre
        pre = cur
        cur = next_node
    return pre


if __name__ == '__main__':    
    values = [1,2,3,4,5]
    list = create_list2(values)
    print_list(list)
    print_list(reverse_list(list))

    list2 = create_list2(values)
    # print_list(list2)
    print_list(reverse_list2(list2))