Как удалить дубликаты из несортированного связанного списка

Question

Я получаю segfault с моей текущей функцией remove_repeats.

Функция remove_repeats:

void remove_repeats(node*& head){
    node* cursor = head;
    node* ptr;
    node* duplicate;

    while(cursor != NULL){
        ptr = cursor;
        while(ptr -> link != NULL){
            if(cursor -> data == ptr -> link -> data){
                duplicate = ptr -> link;
                ptr -> link = ptr -> link -> link;
                delete duplicate;
            }
            ptr = ptr -> link;
        }
        cursor = cursor -> link;
    }
}

main:

int main(){
    int start, stop;
    int split;
    node* head = NULL;
    node *lesser;
    node * greater;

    start = time(NULL);
    build_list(head);
    stop = time(NULL);
    cout<<"Time to build list = "<<stop - start <<"seconds.\n";
    start = time(NULL);
    show_list(head);
    stop = time(NULL);
    cout<<"Time to print list = "<<stop - start<<"seconds.\n";
    cout<<"Size of the list = "<<size(head)<<endl;
    remove_repeats(head);



return 0;
}

В основном, функция build_list создает связанный список из 2000 случайных чисел в диапазоне от 1 до 500.

Функция show_list выводит содержимое связанного списка на экран.

Функция size возвращает количество узлов в связанном списке.

Я думаю, что проблема в том, что данные последних узлов являются повторными, и после этого нет узла, который можно было бы назначить ссылке ptr. Возможно, это не так, но если это так, я не уверен, как с этим справиться.

Answer 1

Этот оператор

ptr = ptr -> link;

должен быть вложенным оператором остальной части предыдущего оператора if. Вот вам.

void remove_repeats( node*&head )
{
    for ( node *cursor = head; cursor != nullptr ; cursor = cursor->link )
    {
        for ( node *ptr = cursor; ptr->link != nullptr; )
        {
            if ( cursor->data == ptr->link->data )
            {
                node *duplicate = ptr->link;
                ptr = ptr->link->link;
                delete duplicate;
            }
            else
            {
                ptr = ptr->link;
            }
        }
    }
}

Определение альтернативной функции может выглядеть следующим образом.

void remove_repeats( node*&head )
{
    for ( node *cursor = head; cursor != nullptr ; cursor = cursor->link )
    {
        for ( node **ptr = &cursor->next; *ptr != nullptr; )
        {
            if ( cursor->data == ( *ptr )->data )
            {
                node *duplicate = *ptr;
                *ptr = ( *ptr )->link;
                delete duplicate;
            }
            else
            {
                ptr = &( *ptr )->link;
            }
        }
    }
}

Answer 2

Если удалить последний элемент связанного списка -> p = p-> link приведет к нулевому указателю

while(ptr -> link != NULL){
            if(cursor -> data == ptr -> link -> data){
                ** delete ptr-> link (which is last element)
            }
            ptr = ptr -> link ( p will be null);
}