本题目摘自《Python程序员面试算法宝典》，我会每天做一道这本书上的题目，并分享出来，统一放在我博客内，收集在一个分类中。
1.2 如何实现链表的逆序
【蚂蚁金服面试题】
难度系数：⭐⭐⭐
考察频率：⭐⭐⭐⭐
题目描述：
给定一个没有排序的链表，去掉其重复项，并保留原顺序，例如链表1 -> 3 -> 1 -> 5 -> 5 -> 7,去掉重复项后变成 1-> 3 -> 5 -> 7
方法一：双重循环
我们从头结点往后以此判断每一个结点，即每一个结点从该结点都往后遍历一遍，往后遍历的过程中，如果有结点和当前结点的值相同，就把这个结点删除掉。
class Node: # 定义一个结点类，每一个结点都有data和next
def __init__(self, data=None):
self.data = data
self.next = None
def remove(first_node): # 这个函数接受的参数是，如果是有头结点的链表传入head.next，没头结点的链表传入head
p = first_node
while p is not None and p.next is not None: # and前面的条件控制了first_node是空的时候进不来
q = p.next # and后面的条件控制了到最后一个元素能够结束
prev = p
while q is not None: # 到最后一个结点还会进行比较一次，
if q.data == p.data: # 如果相等
prev.next = q.next # 直接删掉q
else: # 不相等的时候prev向后移动一个
prev = q
q = q.next
p = p.next
# 测试
data_list = [1, 3, 1, 5, 5, 7]
head = Node(1)
p = head
for data in data_list[1:]: # 按照data_list生成一个单链表
p.next = Node(data)
p = p.next
first_node = head
print("删除前： ", end=' ')
while first_node is not None: # 打印出每一个结点
print(first_node.data, end='\t')
first_node = first_node.next
print()
first_node = head
remove(first_node) # 把重复的结点删除
first_node = head
print("删除后： ", end=' ')
while first_node is not None: # 打印出删除之后的各个结点
print(first_node.data, end='\t')
firtst_node = first_node.next
# 程序输出
删除前： 1 3 1 5 5 7
删除后： 1 3 5 7
这种双重循环的方法的时间复杂度是O(n^2)，相对来说比较慢。
方法二：时间换空间
我们还有一种思路就是，用一个查询很快的容器盛放我们遍历过的结点，如果当前结点在容器中，那么当前结点已经出现过了，就可以把当前结点删除掉，我们可以选用集合set来当作这个容器。
class Node:
def __init__(self, data):
self.data = data
self.next = None
def remove(first_node): # 传参和上面的是一样的
if not first_node.data:
return None
p = first_node.next
s = {first_node.data} # 第一个
prev = first_node
while p is not None:
if p.data in s:
prev.next = p.next
else:
s.add(p.data)
prev = p
p = p.next
# 测试
data_list = [1, 3, 1, 5, 5, 7]
head = Node(1)
p = head
for data in data_list[1:]: # 按照data_list生成一个单链表
p.next = Node(data)
p = p.next
first_node = head
print("删除前： ", end=' ')
while first_node is not None: # 打印出每一个结点
print(first_node.data, end='\t')
first_node = first_node.next
print()
first_node = head
remove(first_node) # 把重复的结点删除
first_node = head
print("删除后： ", end=' ')
while first_node is not None: # 打印出删除之后的各个结点
print(first_node.data, end='\t')
first_node = first_node.next
程序运行结果：
删除前： 1 3 1 5 5 7
删除后： 1 3 5 7
这样我们增加了一个set的空间，但是我们把时间复杂度从O(n^2)直接提到了O(n)。
if hasattr(reader, "QQ"):
print(f"请{reader}加入交流群：6259 88679 !")