本题目摘自《Python程序员面试算法宝典》，我会每天做一道这本书上的题目，并分享出来，统一放在我博客内，收集在一个分类中。
1.1 如何实现链表的逆序
【腾讯笔试题】
难度系数：⭐⭐⭐
考察频率：⭐⭐⭐⭐
题目描述：
给定一个带头结点的单链表，请将其逆序。即如果单链表原来为 head -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，那么逆序后变为 head -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1。
解答
构造结点类和单链表类
class Node:
def __init__(self, data, next):
self.data = data
self.next = next
class SingleLink:
def __init__(self, head):
self.head = head
方法一：就地逆序（推荐，好理解）
主要思路：在遍历链表的时候，修改当前结点的指针域指向，让它指向它的前驱结点。
时间复杂度：O(n)
def reverse(link: SingleLink):
if link.head is None or link.head.next is None:
return None
cur = link.head.next # cur指向第一个结点
pre = link.head # pre指向头结点
while cur.next is not None: # 如果cur不是最后一个结点
ne = cur.next # ne记住当前结点的下一个结点
if pre != link.head: # 如果cur不是第一个结点
cur.next = pre # 把当前结点的next指向前一个结点
else:
cur.next = None
pre = cur # pre结点后移到当前结点
cur = ne # 当前结点后移一位
ne = ne.next # ne结点后移一位
# cur指向tail了
cur.next = pre # 当cur指向了最后一个结点，循环结束，把最后一个结点指向倒数第二个结点
link.head.next = cur # head指向最后一个结点，即cur
方法二：插入法（推荐，好理解）
主要思路：从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，直到遍历结束。
时间复杂度：O(n)
def reverse2(link: SingleLink):
if link.head is None or link.head.next is None: # 空
return link.head
cur = link.head.next.next # 记住第二个结点
link.head.next.next = None # 第一个结点的指针从指向第二个结点变成None
while cur is not None: # 当第二个结点不是None的时候
next = cur.next # next等于第二个结点的next即第三个结点
cur.next = link.head.next # 第二个结点的next指向第一个结点
link.head.next = cur # head的next也从指向第一个结点变成指向第二个结点
cur = next # cur开始指向第三个结点, 如此循环下去
方法三：递归法（不推荐，算法实现难度大，需要额外的压栈和弹栈，有性能下降）
主要思路：先把除了第一个结点以外的结点逆序，接着把第一个结点添加到子链表的后面。
时间复杂度：O(n)
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
def Reverse(head):
if head is None:
return
first_node = head.next
newhead = RecursiveReverse(first_node)
# 将头结点指向逆序后链表的第一个结点
head.next = newhead
return newhead
测试
i = 1
tmp = Node(i, None)
head = Node(None, tmp)
while i < 8:
tmp.next = Node(i, None)
tmp = tmp.next
i += 1
print("正序是: ", end="")
cur = head
while cur.next is not None:
cur = cur.next
print(cur.data, end=" ")
print()
link1 = SingleLink(head)
reverse(link1)
print("逆序是: ", end="")
cur = link1.head
while cur.next is not None:
cur = cur.next
print(cur.data, end=" ")
# 输出：
正序是: 1 1 2 3 4 5 6 7
逆序是: 7 6 5 4 3 2 1 1
欢迎小伙伴们加入我创建的python交流群：625988679
