编写函数RemoveDuplication()的最有效实现

Question

所以我正在学习，我有这个问题，编写函数RemoveDuplication()的最有效实现，它删除了列表中的任何重复。假设列表已排序，但可能存在重复。因此，如果列表最初为
<2,2,5,6,6,6,9>，则函数应该使其为<2,5,6,9>。

我想要删除重复的代码就在这里，我想知道，是否有更有效的方法来删除列表中的重复

template <class T>
void DLList<T>:: RemoveDuplication()
{
    for(DLLNode<T>*ptr = head; ptr!=NULL; ptr=ptr->next)
        while (ptr->val == ptr->next->val)
        {
            ptr->next->next->prev = ptr;
            ptr->next = ptr->next->next;
        }
}

Answer 1

看起来你的代码将运行在0 (n)，这是一个很好的算法。这可能不会更有效率，因为你必须访问每一项才能删除它。

如果你不想删除重复的对象，但是想要返回一个包含非重复对象的新列表，你可以通过将其设置为O(m)使其稍微快一些，其中m是唯一数字的数量，小于或等于n。但我想不出任何方法来做到这一点。

重述一下，有可能稍微快一点，但这很难，而且改进可以忽略不计。

p。当你把它从你的列表中拿出来的时候，不要忘记删除它;)

Answer 2

我认为0 (n)是可以的。然而，最重要的是你的程序会崩溃:-)

for(DLLNode<T>*ptr = head; ptr!=NULL; ptr=ptr->next)
    while (ptr->val == ptr->next->val)

代码区分ptr->next而不检查它是否为!= NULL。因此，算法应该在到达列表的最后一个元素时崩溃。

现在给你一个优化问题:如何在每次迭代时不测试ptr和ptr->next而使程序正确?