这是从链表中删除重复项的有效方法吗？

Question

我正在编写一个函数，它将接受链表的头部，删除所有重复项，并返回新的头部。我已经对其进行了测试，但我想看看您是否可以发现任何错误或对其进行改进。

removeDuplicates(Node head)
    if(head == null) throw new RuntimeException("Invalid linked list");

    Node cur = head.next;
    while(cur != null) {
        if(head.data == cur.data) {
            head = head.next;
        } else {
            Node runner = head;
            while(runner.next != cur) {
                if(runner.next.data == cur.data) {
                    runner.next = runner.next.next;
                    break;
                }
                runner = runner.next;
            }
        cur = cur.next;
    } 
    return head;
}

Answer 1

如果您愿意在进程上花费更多的 RAM，则可以在不改变结构的情况下使其运行得更快。

对于桌面应用程序，我通常喜欢使用更多内存并赢得一些速度。所以我会做这样的事情。

removeDuplicates(Node head) {
    if (head == null) {
        throw new RuntimeException("Invalid List");
    }

    Node current = head;
    Node prev = null;
    Set<T> data = new HashSet<T>(); // where T is the type of your data and assuming it implements the necessary methods to be added to a Set properly.
    while (current != null) {
        if (!data.contains(current.data)) {
            data.add(current.data);
            prev = current;
            current = current.next;
        } else {
            if (prev != null) {
                prev.next = current.next;
                current = current.next;
            }
        }
    }
}

这应该在 O(n) 时间内运行。

编辑

我希望我正确地假设这是某种项目/作业，您被迫使用链接列表，否则，如上所述，您最好使用不同的数据结构。

Answer 2

我没有检查你的代码是否有错误，但我确实有改进它的建议。分配一个将 Node 映射到 Boolean 的 Hashtable 或 HashMap。当您处理每个元素时，如果它不是哈希中的键，请添加它（使用 Boolean.TRUE 作为值）。如果它确实作为密钥存在，那么它已经出现在列表中，您只需将其删除即可。

这比您的方法更快，因为散列查找的工作时间大致恒定，而您有一个内部循环，必须为每个列表元素遍历列表的整个剩余部分。

此外，您可能会考虑使用 equals() 测试而不是 == 是否对您的应用程序更有意义。

Answer 3

为了有效地删除重复项，您应该远离链表：使用 java.util.PriorityQueue 代替；它是一个已排序的集合，您可以为其定义排序标准。如果您总是插入到已排序的集合中，则可以在插入时直接删除重复项，也可以根据需要使用单个 O(n) 传递来删除重复项。

Answer 4

除了使用列表的元素创建哈希映射并使用它作为键来测试每个元素之外，这仅适用于大量元素，其中大取决于所需的资源要创建哈希映射，按顺序扫描列表是一个实用的选择，但还有其他更快的选择。请参阅此处用户138170的答案 - 一个in-地方合并排序是一个O(n log(n))操作，不使用额外的空间，而使用单独分配的数组的解决方案将在O(n)中工作> 时间。实际上，您可能需要分析代码并确定合理的 n 值，，其中 n 是列表中的元素数量，之后分配内存的解决方案将来代替不使用的。

编辑：如果效率确实很重要，我建议不要使用链表（主要是为了保持缓存一致性），也许使用 JNI 并本地实现该功能；数据还必须在本机分配的缓冲区中提供。