按关键词阅读：
题目难度: 简单
原题链接
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述编写代码 ， 移除未排序链表中的重复节点 。 保留最开始出现的节点 。
示例 1:
- 输入：[1, 2, 3, 3, 2, 1]
- 输出：[1, 2, 3]
- 输入：[1, 1, 1, 1, 2]
- 输出：[1, 2]
- 链表长度在[0, 20000]范围内 。
- 链表元素在[0, 20000]范围内 。
- 如果不得使用临时缓冲区 ， 该怎么解决？
- 为了移除重复, 最直观的思路就是使用一个集合存已经访问的节点值
- 然后用双指针 pre 和 cur 一前一后遍历: 如果当前指针 cur 的值已经存在, 就忽略它继续往后, 同时 pre 位置保持不变, 且其 next 指向新的 cur 指针;否则就将当前 cur 的值加入集合中, 并将 pre 和 cur 都往后移动一位
- 时间复杂度 O(N): 需要一次遍历所有节点
- 空间复杂度 O(N): 需要额外的集合来存储节点值
class Solution:def removeDuplicateNodes(self, head: ListNode) -> ListNode:# 方法1: 使用一个set存遍历过的节点值, O(N), O(N)v = set()pre, cur = None, headwhile cur:if cur.val in v:# 当前节点值在集合中, 忽略当前节点, pre位置保持不变cur = cur.nextpre.next = curelse:# 当前节点值不在集合中, 将其加入并移动pre和curv.add(cur.val)pre, cur = cur, cur.nextreturn head方案 2思路- 接下来思考进阶问题: 如何做到不使用临时缓冲区?
- 因为节点排列是无序的, 所以没办法通过比较相邻节点来去重, 只能模拟两重循环了
- 具体做法是外层循环使用一个指针 outer 作为当前起点, 然后内层循环仍利用 pre 和 cur 双指针, 从外层指针处开始向后遍历, 如果当前节点 cur 的值和外层指针值相同的话就删去它
- 时间复杂度 O(N^2): 需要两重循环遍历
- 空间复杂度 O(1): 只使用了几个常数空间的变量
class Solution:def removeDuplicateNodes(self, head: ListNode) -> ListNode:# 方法2: 进阶, 外层循环指针+内层循环双指针, O(N^2), O(1), 遍历后面所有节点看是否有相同的, 有的话全部删除# 没有O(N)算法可以做到不使用额外空间去重..if not head:return None# outer是外层循环指针outer = headwhile outer:# 内层循环需要两个指针来遍历和删除pre, cur = outer, outer.nextwhile cur:if cur.val == outer.val:# 遇到重复值了, 删除cur节点cur = cur.nextpre.next = curelse:# 没有遇到重复, pre和cur依次向后移动一位pre, cur = cur, cur.next# 外层指针后移outer = outer.nextreturn head
稿源：(未知)
【傻大方】网址：http://www.shadafang.com/c/111T312102020.html
标题：程序员面试金典 - 面试题 02.01. 移除重复节点