题目难度: 简单
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例 1:
- 输入：[1, 2, 3, 3, 2, 1]
- 输出：[1, 2, 3]
示例 2:
- 输入：[1, 1, 1, 1, 2]
- 输出：[1, 2]
提示：
- 链表长度在[0, 20000]范围内。
- 链表元素在[0, 20000]范围内。
题目思考
- 如果不得使用临时缓冲区，该怎么解决？
解决方案
方案 1
思路
- 为了移除重复, 最直观的思路就是使用一个集合存已经访问的节点值
- 然后用双指针 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, head
while cur:
if cur.val in v:
# 当前节点值在集合中, 忽略当前节点, pre位置保持不变
cur = cur.next
pre.next = cur
else:
# 当前节点值不在集合中, 将其加入并移动pre和cur
v.add(cur.val)
pre, cur = cur, cur.next
return 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 = head
while outer:
# 内层循环需要两个指针来遍历和删除
pre, cur = outer, outer.next
while cur:
if cur.val == outer.val:
# 遇到重复值了, 删除cur节点
cur = cur.next
pre.next = cur
else:
# 没有遇到重复, pre和cur依次向后移动一位
pre, cur = cur, cur.next
# 外层指针后移
outer = outer.next
return head 大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号