python经典面试算法题1.2:如何从无序链表中移除重复项

时间:2024-07-08 09:32:56

本题目摘自《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 !")