C++ - 单链表 - 想法

Question

我想编写一种方法来从单链表中删除具有重复数据值的连续项。该方法应返回删除的项目数。该方法应该根据需要清理内存，并且应该假设内存是使用 new 分配的。

例如传入列表
->a->b->c->c->a->b->b->b->a->null 应该导致
->a->b->c->a->b->a->null 并返回 3

列表项定义和函数声明如下所示

struct litem { 字符数据； 下一个项目*； };

int remove_consecutive_duplicates(item*&列表);

I have a simple logic to check the next element recursively & removing the element if its duplicate. 
But, i would like to know how many efficient ways to do this ?  All ideas welcome from C++ gurus..

Answer 1

您可以使用 std::list，在将元素推入其上之前，您必须检查：

if ((*l.rbegin()) == next)
{
    return;
}

l.push_back(next);

Answer 2

在元语言中：

item = items.first
while (item != null) {
    while (item.next != null && item.value = item.next.value) {
        temp = item.next
        item.next = item.next.next
        temp.dispose
    }
    item = item.next
}

Answer 3

据我所知，这里没有太多需要优化的地方。返回使用的项目数只是递增计数器的一种情况。基本上，如果您发现 litem->data == litem->next->data，那么您需要像这样进行删除：

litem* tmpItem = currentItem->next;
currentItem->next = tmpItem->next;
delete tmpItem;

继续迭代直到 currentItem->next == NULL，以避免引用超出列表末尾。