题目描述：
给定一个带头节点的单链表，将其逆序。即如果单链表原来为head->1->2->3->4->5->6->7，那么逆序后变为head->7->6->5->4->3->2->1。
分析：
单链表只能从头节点开始遍历，修改节点指针域时，记录下后继节点的地址，否则会丢失后继节点。
方法一：就地逆序
思路：遍历链表，修改当前节点的指针域为指向其前驱节点。用两个指针变量分别保存前驱节点、后继节点的地址。注意首尾节点的特殊处理。
实现：
class LNode:
def __new__(self, x):
self.data = x
self.next = None
# 实现链表逆序，输入head链表头节点
def Reverse(head):
# 判断链表是否为空
if head == None or head.next == None:
return
pre = None# 前驱节点
cur = None# 当前节点
next = None# 后继节点
# 把链表首节点变为尾节点
cur = head.next
next = cur.next
cur.next = None
pre = cur
cur = next
# 使当前遍历到的节点cur指向其前驱节点
while cue.next != None:
next = cur.next
cur.next = pre
pre = cur
cur = cur.next
cur = next
cur.next = pre
head.next = cur
算法性能分析：对链表只遍历一次，时间复杂度为O(N)，O为链表长度。需要常数个额外变量保存当前节点的前驱、后继节点，空间复杂度为O(1)。
方法二：递归法
思路：先逆序除第一个节点之外的子链表，接着把节点1添加到逆序的子链表之后
实现：
# 对不带头节点的链表进行逆序
# 输入为firstRef: 链表首结点
def RecursiveReverse(head):
# 如果链表为空或者只有一个元素
if head is None or head.next is None:
return head
else:
# 反转后面的节点
newhead = RecursiveReverse(head.next)
# 把当前遍历的节点加到后面节点逆序后链表的尾部
head.next.next = head
head.next = None
return newhead
# 对带头节点的链表逆序
# 输入head为头节点
def Reverse(head):
if head is None:
return
# 获取链表第一个节点
firstNode = head.next
# 对链表进行逆序
newhead = RecursiveReverse(firstNode)
head.next = newhead
return newhead
算法性能分析：一次遍历，时间复杂度为O(N)，N为链表长度。额外的压栈出栈导致性能下降。
方法三：插入法
思路：
从链表的第二个节点开始，把遍历到的节点插入到头节点的后边，直到遍历结束。
实现：
def Reverse(head):
# 判断链表是否为空
if head is None or head.next is None:
return
cur = None# 当前节点
next = None# 后继节点
cur = head.next.next
# 设置链表第一个节点为尾节点
head.next.next = None
# 把遍历到的节点插入到头节点的后面
while cur is not None:
next = cur.next
cur.next = head.next
head.next = cur
cur = next
算法性能分析：一次遍历，时间复杂度为O(N)，N为链表长度。与方法一相比，不需要额外空间存储前驱节点，与方法二相比，不需要执行压栈出栈操作。
