python经典面试算法题1.2:如何从无序链表中移除重复项
2024-10-21 13:32:32
本题目摘自《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 !")
最新文章
- HTML5快速入门(三)—— 标签综合运用
- .net下Ueditor配置(主要讲解上传功能配置)
- [转]Sql server2005中如何格式化时间日期
- 如何使java中double类型不以科学计数法表示
- 听同事讲 Bayesian statistics: Part 2 - Bayesian inference
- 从头开始学c++,补基础,补踏实
- android gridview画分割线
- Python学习--13 文件I/O
- Leetcode题解(23)
- Angular-Mobile介绍
- 笔记:Maven 插件配置 - maven-jar-plugin
- [编译] 4、在Linux下搭建nRF51822的开发烧写环境(makefile版)
- Android 系统版本和API level的关系表
- QSS 记录
- 20164319 刘蕴哲 Exp4:恶意代码分析
- Android Studio导入jar包
- Oracle+PL+SQL从入门到精通.丁士锋.清华大学出版社.2012
- 博客搬家了,新域名dinphy.wang
- spring-cloud-config-server——Environment Repository
- scrapy框架学习之路
热门文章
- LeetCode_155-Min Stack
- BZOJ [Scoi2015]情报传递
- Java自动化测试框架-02 - TestNG之理论实践 - 纸上得来终觉浅,绝知此事要躬行(详细教程)
- Web安全之变量覆盖漏洞
- Neo4j:图数据库GraphDB(二)高级查找
- PHP krsort
- 记一次EF Core DBContext在Action委托中GC异常的问题.
- 【原创】(九)Linux内存管理 - zoned page frame allocator - 4
- 解决Zend OPcache huge_code_pages: mmap(HUGETLB) failed: Cannot allocate memory报错
- 玩转OneNET物联网平台之MQTT服务⑤ —— OneNet智能灯+MVP框架