我正在编写一个函数,该函数将接受链表的开头,删除所有重复项,然后返回新的开头。我已经对其进行了测试,但是我想看看您是否可以捕获任何错误或对其进行改进。
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)时间内运行。
编辑
我希望我假设这是某种项目/作业,在这种情况下您被迫使用链表是正确的,否则,如上所述,最好使用其他数据结构。