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