CODEWITHSUNDEEP
c++data-structureslinked-list
user2891869
user2891869

Reputation: 609

Deleting duplicate values in a sorted linked list with repeating same values

I have encountered a problem printing sorted linked lists after deleting those values that are repeating more than 1 time.

Code:

Node* RemoveDuplicates(Node *head)
{
    Node *prev,*cur;
    cur=head;
    while(cur->next!=NULL)
        {
        prev = cur;
        cur = cur->next;
        if(prev->data == cur->data)
            {
            prev->next = cur->next;
            free(cur);
        }
    }
    return head;
}

This deletes values that occur more than once, but for more than that it does not work and I am unable to find why.

Test cases:

For eg : if INPUT is like this :

4
6
1 2 2 3 3 4
7
1 1 1 1 1 1 1
5
2 3 3 4 6
1
10

Then it should have OUTPUT like this :

1 2 3 4
1
2 3 4 6
10

But my OUTPUT is :

1 2 3 4
1 1 1 1
2 3 4 6
10

Upvotes: 1

Views: 855

Answers (3)

bluecliff
bluecliff

Reputation: 67

As cur is freed,it could not be accessed in while. You can do like this:

Node* RemoveDuplicates(Node *head)
{
    if(head==NULL){
        return NULL;
    }
    Node *prev,*cur;
    cur=head;
    while(cur->next!=NULL)
    {
        prev = cur;
        cur = cur->next;
        if(prev->data == cur->data)
        {
            prev->next = cur->next;
            free(cur);
            cur = prev;
        }
    }
    return head;
}

Upvotes: 1

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521103

Here is a revamped version of your code which I believe will run without problems. I added a NULL check at the beginning and I modified the algorithm to correctly handle duplicates:

Node* RemoveDuplicates(Node *head)
{
    if (head == NULL)         // return NULL in case of empty list
        return NULL;

    if (head->next == NULL)   // return the head in case of list with only one element
        return head;

    Node *prev,*cur;
    prev = head;
    cur  = head->next;

    while (cur != NULL)
    {
        if (prev->data != cur->data) {
            prev->next = cur;
            prev = cur;    
            cur = cur->next;
        }
        else {
            Node* temp = cur;
            cur = cur->next;
            free(temp);       // delete a duplicate node
        }
    }

    prev->next = NULL;        // NULL-terminate the modified list

    return head;
}

Upvotes: 0

Blastfurnace
Blastfurnace

Reputation: 18652

This is one possible method. The basic idea is to walk the list and as long as there is a next node and the data matches snip the next node out of the list. I've added a DeleteNode() helper function that frees a node and returns it's old next pointer. This utility is useful in other contexts.

Node* DeleteNode(Node *node)
{
    Node *ptr = node->next;
    delete node; // This is C++, you might need free() instead
    return ptr;
}

Node* RemoveDuplicates(Node *list)
{
    Node *node = list;
    while (node) {
        while (node->next && (node->data == node->next->data)) {
            node->next = DeleteNode(node->next);
        }
        node = node->next;
    }
    return list;
}

Upvotes: 1

Related Questions