Trying to fix error in a program for removing duplicates in linked list

Question

I am executing a program for removing duplicates from an unsorted linked list using two loops.

The program includes two structs for defining Node and newNode. Also, it includes two user-defined functions removeDuplicates for removing duplicates of linked-list and printList for printing the list.

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");
}

I ran a couple of test cases,

case 1 Input : 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);
}

case 2 Input : 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);
}

The program works for one test case and not other case. What am I missing in the code?

Have you tried running your code line by line in a debugger while monitoring the values of all variables? If not, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas Wenzel, Aug 06 '20 at 17:03
Don't do `delete(dup);` You are not doing `new` anywhere. Also, make a [mre] — cigien, Aug 06 '20 at 17:05
Shouldn't the line `ptr1 = ptr1->next;` be at the end of the outer loop? Currently, it is at the end of the inner loop. — Andreas Wenzel, Aug 06 '20 at 17:15
@Andreas Yes, It worked. Thanks for suggesting the debugging links. — Madhumitha, Aug 06 '20 at 17:19
Warning: It looks like someone may be teaching you C and telling you it is C++. Do not be fooled. [Upgrade your reference materials](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) so that you can be aware of the differences. — user4581301, Aug 06 '20 at 17:30
If you make a slightly smarter `newNode`, `Node *newNode(int data, Node * next){ Node *temp = new Node; temp->data = data; temp->next = next; return temp; }` the huge mass of `start->next->next->next->next->next->next`s can be reduced to something like `start = newNode(1, newNode(2, newNode(3, NULL)))` — user4581301, Aug 06 '20 at 17:36

score 2 · Accepted Answer · answered Aug 06 '20 at 17:21

The issue is here:

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

You are moving ptr1 inside the loop that removes the duplicates, but it needs to be moved once per node in the linked-list:

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

Here's a demo.

score 1 · Answer 2 · answered Aug 06 '20 at 17:27

/* 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;
    }  
}

Note: you can greatly reduce the amount of book-keeping required with a pointer-to-pointer. See the Community Addition [in this answer.](https://stackoverflow.com/a/22122095/4581301) — user4581301, Aug 06 '20 at 17:32

score 0 · Answer 3 · answered Aug 06 '20 at 18:06

Short answer. The below code will work.

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;
    }
}

You are modifying the variable ptr1 inside the first while loop. Since you have to compare the first element with all the remaining elements of the linked list, you should only change 'ptr1' after the internal while loop is finished. Otherwise, the first node will be compared with the second node and then the first node will be modified to the next node. So the first node will not get compared with other nodes.

Trying to fix error in a program for removing duplicates in linked list

3 Answers3