1.翻转链表

#coding=utf-8
class Node(object):
    def __init__(self,data,next=None):
        self.data = data
        self.next = None

def travel(head):
    curr = head
    while curr is not None:
        print(curr.data)
        curr = curr.next

node1=Node(1)
node2=Node(2)
node3=Node(3)

node1.next=node2
node2.next=node3

travel(node1)

# pre = None
# head = node1
# curr = node1
#
# while curr is not None:
#     tmp = curr.next
#     curr.next=pre
#     pre = curr
#     curr = tmp


def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next) # 翻转下个节点开头的小链表，返回头节点
    # 修改节点指向
    next_node = head.next
    next_node.next = head
    # 置空head节点，防止链表循环
    head.next = None
    return new_head


pre = reverse(node1)
travel(pre)