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

Question

Я выполняю программу для удаления дубликатов из несортированного связного списка с использованием двух циклов.

Программа включает два structs для определения Node и newNode. Кроме того, он включает в себя две пользовательские функции removeDuplicates для удаления дубликатов связанного списка и printList для печати списка.

struct Node {
       int data;
       struct Node *next;
};

struct Node *newNode(int data) {
       Node *temp = new Node;
       temp->data = data;
       temp->next = NULL;

       return temp;
};

/* Function to remove duplicates from an unsorted linked list */
void removeDuplicates(struct Node *start) {
     struct Node *ptr1, *ptr2, *dup;
     ptr1 = start;

     while (ptr1 != NULL && ptr1->next != NULL) {
           ptr2 = ptr1;

           while (ptr2->next != NULL) {
                 if (ptr1->data == ptr2->next->data) {
                    dup = ptr2->next;
                    ptr2->next = ptr2->next->next;
                    delete (dup);
                 } else
                    ptr2 = ptr2->next;

                 ptr1 = ptr1->next;
           }
     }
}

void printList(struct Node *node) {
     while (node != NULL) {
           printf("%d  ", node->data);
           node = node->next;
     }

     printf("\n");
}

Я выполнил несколько тестовых примеров,

случай 1 Ввод: 12-> 11-> 12-> 21-> 41-> 43-> 21

   Output(from the program) : 12->11->12->21->41->43->21
       Required Output : 12->11->21->41->43

int main() {
    struct Node *start = newNode(12);
    start->next = newNode(11);
    start->next->next = newNode(12);
    start->next->next->next = newNode(21);
    start->next->next->next->next = newNode(41);
    start->next->next->next->next->next = newNode(43);
    start->next->next->next->next->next->next = newNode(21);

    printf("Linked List before removing duplicates");
    printList(start);

    removeDuplicates(start);

    printf("Linked List after removing duplicates");
    printList(start);
}

случай 2 Ввод: 10-> 12-> 11-> 11-> 12-> 11-> 10

       Output : 10->12->11

int main() {
    struct Node *start = newNode(10);
    start->next = newNode(12);
    start->next->next = newNode(11);
    start->next->next->next = newNode(11);
    start->next->next->next->next = newNode(12);
    start->next->next->next->next->next = newNode(11);
    start->next->next->next->next->next->next = newNode(10);

    printf("Linked List before removing duplicates");
    printList(start);

    removeDuplicates(start);

    printf("Linked List after removing duplicates");
    printList(start);
}

Программа работает для одного теста, а не для другого. Что мне не хватает в коде?

Answer 1

Проблема здесь:

while ((ptr1 != NULL) && (ptr1->next != NULL))
{
        ptr2 = ptr1;
        while (ptr2->next != NULL)
        {
            // delete if duplicate
            ptr1 = ptr1->next;
        }
}

Вы перемещаете ptr1 внутри l oop, который удаляет дубликаты, но его нужно перемещать один раз для каждого узла в связанном списке:

while ((ptr1 != NULL) && (ptr1->next != NULL))
{
        ptr2 = ptr1;
        while (ptr2->next != NULL)
        {
            // delete if duplicate
        }
        ptr1 = ptr1->next;  // move ptr1 here
}

Вот демо .

Answer 2

/* Function to remove duplicates from an unsorted linked list*/
void removeDuplicates(struct Node *start)
{
    struct Node *ptr1 = start;

    while (ptr1) {
   
        struct Node *ptr2     = ptr1->next;
        struct Node *ptr2prev = ptr1;

        while (ptr2) {

            if (ptr1->data == ptr2->data) {
                
                struct Node *tmp = ptr2;

                ptr2prev->next   = ptr2->next;
                ptr2             = ptr2->next;
                
                delete tmp;
                continue;
            }  

            ptr2 = ptr2->next;
            ptr2prev = ptr2prev->next;
        }  

        ptr1 = ptr1->next;
    }  
}

Answer 3

Короткий ответ. Приведенный ниже код будет работать.

void removeDuplicates(struct Node *start)
{
    struct Node *ptr1, *ptr2, *ptr3;
    ptr1 = start;
    while ((ptr1 != NULL) )
    {
        ptr2 = ptr1->next;
        ptr3=ptr1; //used inside the next while loop
        while (ptr2 != NULL)
        {
            if ((ptr1->data) == (ptr2->data))
            {
                ptr3->next = ptr2->next;
                delete (ptr2);
                ptr2 = ptr3->next
            }
            else
            {
                ptr3 = ptr2; //prev of next ptr2
                ptr2 = ptr2->next;
            }
        }
        ptr1=ptr1->next;
    }
}

Вы изменяете переменную ptr1 внутри первого, а l oop. Поскольку вам нужно сравнить первый элемент со всеми остальными элементами связанного списка, вам следует изменить «ptr1» только после завершения внутреннего, пока l oop завершено. В противном случае первый узел будет сравниваться со вторым узлом, а затем первый узел будет изменен на следующий узел. Таким образом, первый узел не будет сравниваться с другими узлами.