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? You may also want to read this: How to debug small programs — Andreas Wenzel
– Andreas Wenzel, Commented Aug 6, 2020 at 17:03
Don't do delete(dup); You are not doing new anywhere. Also, make a minimal reproducible example — cigien
– cigien, Commented Aug 6, 2020 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
– Andreas Wenzel, Commented Aug 6, 2020 at 17:15
Warning: It looks like someone may be teaching you C and telling you it is C++. Do not be fooled. Upgrade your reference materials so that you can be aware of the differences. — user4581301
– user4581301, Commented Aug 6, 2020 at 17:30

cigien · Accepted Answer · 2020-08-06 17:21:38Z

2

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.

answered Aug 6, 2020 at 17:21

cigien

61.2k11 gold badges86 silver badges124 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ali Askari · Accepted Answer · 2020-08-06 17:27:23Z

1

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

answered Aug 6, 2020 at 17:27

Ali Askari

5353 silver badges8 bronze badges

2 Comments

user4581301 Over a year ago

Note: you can greatly reduce the amount of book-keeping required with a pointer-to-pointer. See the Community Addition in this answer.

Ali Askari Over a year ago

@user4581301. Thanks

Manoj AV · Accepted Answer · 2020-08-06 18:06:15Z

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.

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related