#!/usr/bin/env python
"""Reverse linked list."""
 
 
class Node:
    """Linked list is either None or a value and a link to the next list."""
 
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
head = Node(1, Node(2, Node(3, Node(4))))
 
 
def print_list(head, end='\n'):
    while head:
        print(head.data, end=' -> ' if head.next else '')
        head = head.next
    print(end=end)
 
 
print_list(head)
 
 
def reverse_list(head, tail=None):
    while head:
        head.next, tail, head = tail, head, head.next
    return tail
 
 
print_list(reverse_list(head))
 

IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiIiIlJldmVyc2UgbGlua2VkIGxpc3QuIiIiCgoKY2xhc3MgTm9kZToKICAgICIiIkxpbmtlZCBsaXN0IGlzIGVpdGhlciBOb25lIG9yIGEgdmFsdWUgYW5kIGEgbGluayB0byB0aGUgbmV4dCBsaXN0LiIiIgoKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBkYXRhLCBuZXh0PU5vbmUpOgogICAgICAgIHNlbGYuZGF0YSA9IGRhdGEKICAgICAgICBzZWxmLm5leHQgPSBuZXh0CgoKaGVhZCA9IE5vZGUoMSwgTm9kZSgyLCBOb2RlKDMsIE5vZGUoNCkpKSkKCgpkZWYgcHJpbnRfbGlzdChoZWFkLCBlbmQ9J1xuJyk6CiAgICB3aGlsZSBoZWFkOgogICAgICAgIHByaW50KGhlYWQuZGF0YSwgZW5kPScgLT4gJyBpZiBoZWFkLm5leHQgZWxzZSAnJykKICAgICAgICBoZWFkID0gaGVhZC5uZXh0CiAgICBwcmludChlbmQ9ZW5kKQoKCnByaW50X2xpc3QoaGVhZCkKCgpkZWYgcmV2ZXJzZV9saXN0KGhlYWQsIHRhaWw9Tm9uZSk6CiAgICB3aGlsZSBoZWFkOgogICAgICAgIGhlYWQubmV4dCwgdGFpbCwgaGVhZCA9IHRhaWwsIGhlYWQsIGhlYWQubmV4dAogICAgcmV0dXJuIHRhaWwKCgpwcmludF9saXN0KHJldmVyc2VfbGlzdChoZWFkKSkK