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

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) 时间内运行。

编辑

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