Aug 282012
 

Given a linked list, write code to remove duplicates from the list.

Input : 1->3->4->4->6->6->6->7
Output: 1->3->4->6->7

Input : 4->1->4->4
Output: 4->1


If List is Sorted:

If it is given that the list is sorted. Then removing duplicates from the list is easier.

For each node in the list
  IF next node is same as current node
      delete next node

Code:

/**
 * Remove duplicate nodes from the sorted linked list
 *
 * We don't need to take Node** because the first node will never be deleted.
 */
void removeDuplicates(Node* head)
{
    while(head != NULL)
    {
        if(head->link != NULL)
        {
            while(head->link != NULL && head->link->data == head->data)
            {
                Node* temp = head->link;
                head->link = temp->link;
                delete temp;
            }
        }
        head = head->link;
    }
}

If List is Unsorted:

Removing duplicates from an unsorted list is little complicated. The brute-force method, using two loops, will take O(n2) time

FOR each node in the list
    Traverse the list (following the node)
        If any node has the same value as the Node in outer loop
            Remove Node

Code:

void removeDuplicates(Node *head)
{
    struct Node *ptr2, *dup;

    while(head != NULL)
    {
        Node* ptr = head;

        while(ptr->next != NULL)
        {
            if(head->data == ptr->next->data)
            {
                Node *temp = ptr->next;
                ptr->next = temp->next;
                delete temp;
            }
            else
            {
                ptr = ptr->next;
            }
        }
        head = head->next;
    }
}

Another method can be to actually sort the list first and then remove the duplicate nodes from the list.

A further improved method can be to store the Nodes in the hash. When the Node is encountered for the first time during traversing, its entry will be put in the Hash, when a duplicate comes, the entry will be already in the Hash, hence remove the Node.

FOR each node in the linked list
    IF Node exist in the Hash
        delete the Node
    ELSE
        put the Node in the hash

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)