Part 22 of 26 in Linked List - set 02  

Remove duplicates from a sorted linked list by admin

Problem statement

Given a singly linked list of integers that is sorted, remove all duplicates from the list.

Input

You need to write a method named "RemoveDuplicates" that will take only one parameter - pointer to the head of the linked list. The list will have at least one element and will never be NULL/empty.

Output

Return type of the method will be void. You need to modify the given list only and address of the head node should not change.

The list given to us is already sorted. This means that the nodes with the same data will be placed continuously in the list. We will use this idea to remove the duplicate elements in the code.

The basic idea is to iterate through each node in the list. Then if the data of the next node is equal to the data in the current node, we will delete the next node. Lets take the following example where value of k = 3.

      1 -> 3 -> 3 -> 8 -> 10 -> NULL 

When we reach the second node of the list with value '3', the data in the next node is equal to the data in the current node. So, we need to keep only one among these two nodes. We will stay on the current node and delete the next node. So, we assign the next pointer of node with value '3' (2nd node in the list) to the node with value '8'. This pointer to node with value '8' is actually stored in the 'next' pointer of the node with value '3' (3rd node int the list). So, we assign the 'next' pointer of the current node to the 'next' pointer of the next node in the list which is the node with value '3' (3rd node in the list).

Then our modified list will look like this:

	1 -> 3 -> 8 -> 10 -> NULL	   

We will keep on doing this until the data in the next node is not equal to the data in the current node. If it is not equal, then we can understand that all the duplicate elements of the current data is deleted, and we can move to the next node.

editorial written by i_coder

/*
  Remove all duplicate elements from a sorted linked list
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
void RemoveDuplicates(Node *head)
{
  //Exxecute the loop until we reach the end of the list
   while(head -> next != NULL){
      //If the data in the current node is equal to the data
      //in the next node, then we delete the next node and remain in
      //the same node.
      if(head -> data ==  (head -> next) -> data){
        head -> next = (head -> next) -> next;
        continue;
      }
      //If the data is not equal to the next node, then we move to
      //next node.
    head = head -> next;
  }
}

featured solution by i_coder



To try out your code



Sign in

Sign up