当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.程序员面试金典.0201.Remove Duplicate Node 移除重复节点

LeetCode.程序员面试金典.0201.Remove Duplicate Node 移除重复节点

题目描述

《程序员面试金典(第 6 版)》面试题 02.01. 移除重复节点
https://leetcode-cn.com/problems/remove-duplicate-node-lcci/

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

示例1:

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

示例2:

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

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

进阶:
如果不得使用临时缓冲区,该怎么解决?


解题过程

哈希Map空间O(n)

用 set 记录结点值是否出现过,出现过则删除当前节点,否则加入 set
由于首节点不可能被删除,也不需要额外的 dumbHead 代替首节点。

时间复杂度 O(n),空间复杂度 O(n)

private static class SolutionV202006 {
    public ListNode removeDuplicateNodes(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        Set<Integer> visited = new HashSet<>();
        ListNode cur = head, pre = null;
        while (cur != null) {
            if (visited.contains(cur.val)) {
                pre.next = cur.next;
                cur.next = null;
                cur = pre.next;
            } else {
                visited.add(cur.val);
                pre = cur;
                cur = cur.next;
            }
        }
        return head;
    }
}

双重循环空间O(1)


GitHub代码

algorithms/leetcode/crack/_0201_RemoveDuplicateNode.java
https://github.com/masikkk/algorithms/blob/master/leetcode/crack/_0201_RemoveDuplicateNode.java


上一篇 LeetCode.209.Minimum Size Subarray Sum 长度最小的子数组

下一篇 Linode VPS 使用记录

阅读
评论
290
阅读预计1分钟
创建日期 2020-06-26
修改日期 2020-06-26
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论