我正在编写一个函数,该函数将接受链表的开头,删除所有重复项,然后返回新的开头。我已经对其进行了测试,但是我想看看您是否可以捕获任何错误或对其进行改进。

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;
}

最佳答案

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

对于台式机应用程序,我通常倾向于使用更多的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)时间内运行。

编辑

我希望我假设这是某种项目/作业,在这种情况下您被迫使用链表是正确的,否则,如上所述,最好使用其他数据结构。

09-25 22:31
查看更多