题目难度: 简单

原题链接

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

题目描述

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

示例 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