单链表逆置的思路
a：将单链表储存为数组，然后按照数组的索引逆序进行反转。
b：使用3个指针遍历单链表，逐个链接点进行反转。
c：从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。
d: 递归(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)
具体实现
pre指向前一个结点，cur指向当前结点，next指向下一个节点。
循环实现
class Node(object):
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# 使用for循环并不能生成链表
# for i in range(1,10):
# link = Node(i)
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
def rev(link):
pre = link
cur = link.next
pre.next = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
root = rev(link)
while root:
print(root.data)
root = root.next
递归实现
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# 递归，head为原链表的头结点，newhead为反转后链表的头结点
def recurse(head, newhead):
if head is None:
return
if head.next is None:
newhead = head
else:
newhead = recurse(head.next, newhead)
head.next.next = head
head.next = None
return newhead
# 建立链表1->2->3->4->None
head = ListNode(1)
p1 = ListNode(2)
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
newhead = None
# 输出链表4->3->2->1->None
p = recurse(head, newhead)
while p:
print(p.val)
p = p.next
