被压抑的情感并不会消失，累积到一定程度后，反而以更丑恶的方式爆发出来，有些精神病就是这样造成的。若是一味压抑，不能把愤懑的情绪加以升华，自我评价将日趋低落。——《高效能人士的七个习惯》
这段话告诉我们，心里有事一定要说出来，找人倾诉，或者写出来。或者是bug出多了，会被气炸，甚至砸了这破电脑……我们还是努力学习吧！
题目:给定一个带头节点的单链表：head->1->2->3->4->5->6->7->8；使其成为：head->8->7->6->5->4->3->2->1。
今天的题目还是将单链表逆序，前面已经写过两种方法了，一篇就地逆序法,一篇递归法。就地逆序法是将遍历到的节点逆序，需要将整个链表遍历一遍，时间复杂度为O(n),需要常数个额外变量来保存当前节点的前驱节点和后继节点，因此空间复杂度为O(1)。
递归法在性能上要比就地逆序法差一点。其优点是思路直观，很容易理解；但是其缺点就是实现起来要难一点，还有一点就是Python支持的递归深度为默认是 1000，在昨天的代码中，我将链表的长度加到998就是极限了，会报出下面图中的错误。
递归溢出
经过查找资料，这是python专门设置的一种机制用来防止无限递归造成Python溢出崩溃，默认深度是可以改的：
import sys
sys.setrecursionlimit(1500) # 这是将递归深度改为1500
好的，今天的方法是插入法。
插入法的主要思路是，从链表的第二个节点开始遍历，将遍历到的当前节点插入到头节点的后面，直到遍历完所有节点。即原链表为head->1->2->3->4->5->6->7->8，从2开始遍历，将其插入1前面，也就是头节点后面：head->2->1->3->4->5->6->7->8，然后遍历到3，同理将其插入到头节点后面。当所有节点都插入头节点head后面，就可以实现链表的逆序。
我们要逆序链表当然得现有一个链表，链表的构造方法我在昨天文章写了，看不懂可以看看—— python算法-002单链表逆序递归法 ,下面代码实现：
#先构造节点对象
class LNode:
"""
定义链表对象
"""
def __init__(self, x):
self.data = x
self.next = None
#构造链表函数
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
tmp = LNode(i)
cur.next = tmp
cur = tmp
i += 1
链表有了，接下来就是实现算法：
def Reverse(head):
'''
带头节点
输入: 链表
输出: 逆序后的链表
'''
#先判断链表是否为空或这只有一个元素，是则返回
if head is None or head.next is None:
return head
cur = None # 用来遍历链表
next = None # 用来指向当前节点的后继节点
cur = head.next.next # 从链表的第二个节点开始遍历
head.next.next= None # 断开第一个节点与第二个节点。
# 注意这里是重点！一定要断开，因为不断开的话，在下一步中
# 第二个节点的next域为第一个节点，但是第一个节点的next域为第二个节
# 点，这就成了一个最小的环，那么后面的程序就进入了死循环
while cur is not None:
next=cur.next # next用来保存cur的后继节点，不然会丢失后面的节点
cur.next=head.next # 将当前遍历的节点插入到头节点之后
head.next = cur #这里的两步实现的“插入”，细细体会
cur = next # 遍历下一个节点
return head
算法到这里就写完了，下面我们来试一试这个算法：
if __name__=='__main__':
# 构造链表
head=creatLink(8)
#打印逆序前的链表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
print("\nAfterReverse:")
#调用逆序函数
head=Reverse(head)
#打印逆序后的链表
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
这是运行成果：
程序运行结果
给一下全部的代码：
#先构造节点对象
class LNode:
"""
定义链表对象
"""
def __init__(self, x):
self.data = x
self.next = None
#构造链表函数
def creatLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
tmp = LNode(i)
cur.next = tmp
cur = tmp
i += 1
def Reverse(head):
'''
带头节点
输入: 链表
输出: 逆序后的链表
'''
#先判断链表是否为空或这只有一个元素，是则返回
if head is None or head.next is None:
return head
cur = None # 用来遍历链表
next = None # 用来指向当前节点的后继节点
cur = head.next.next # 从链表的第二个节点开始遍历
head.next.next= None # 断开第一个节点与第二个节点。
# 注意这里是重点！一定要断开，因为不断开的话，在下一步中
# 第二个节点的next域为第一个节点，但是第一个节点的next域为第二个节
# 点，这就成了一个最小的环，那么后面的程序就进入了死循环
while cur is not None:
next=cur.next # next用来保存cur的后继节点，不然会丢失后面的节点
cur.next=head.next # 将当前遍历的节点插入到头节点之后
head.next = cur #这里的两步实现的“插入”，细细体会
cur = next # 遍历下一个节点
return head
if __name__=='__main__':
# 构造链表
head=creatLink(8)
#打印逆序前的链表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
print("\nAfterReverse:")
#调用逆序函数
head=Reverse(head)
#打印逆序后的链表
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
好了，今天的算法是对有头节点的链表写的，不带头节点的你会吗？欢迎来讨论，在我的github上也有代码，你可以对照一下，亦可以将你的代码发我给我、私信我，也可以关注我自己的公众号：DKider 来联系我。
我们一起加油吧！
力学如力耕，勤惰尔自知。但使书种多，会有岁稔时。——宋 刘过《书院》
网友评论