程序员面试金典 - 面试题 02.01. 移除重复节点

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

示例 1:

  • 输入:[1, 2, 3, 3, 2, 1]
  • 输出:[1, 2, 3]

示例 2:

  • 输入:[1, 1, 1, 1, 2]
  • 输出:[1, 2]

提示:

  • 链表长度在[0, 20000]范围内。
  • 链表元素在[0, 20000]范围内。

题目思考

  1. 如果不得使用临时缓冲区,该怎么解决?

解决方案

方案 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

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

每日精选算法题 文章被收录于专栏

每日精选几道算法题代码+题解, 祝你offer满满

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议