C++ - Single Linked List - Ideas

Question

I want to write a method to remove consecutive items with duplicate data values from a singly linked list. The method should return the number of items removed. The method should clean up memory as required, and should assume that memory was allocated using new.

For example, passing in the list
->a->b->c->c->a->b->b->b->a->null should result in
->a->b->c->a->b->a->null and return 3

The list item definition and function declaration are given below

struct litem { char data; litem* next; };

int remove_consecutive_duplicates( litem*& list );

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

You can use std::list, and before pushing element on it you must check:

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

l.push_back(next);

Answer 2

As far as I can see, there's not a lot to optimize here. Returning the number of items used is just a case of incrementing a counter. Basically, if you find that litem->data == litem->next->data, then you need to do the removal like so:

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

Keep iterating until currentItem->next == NULL, to avoid referencing beyond the end of the list.

Answer 3

in meta language:

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
}