{"id":3858,"date":"2021-08-16T13:05:20","date_gmt":"2021-08-16T13:05:20","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3858"},"modified":"2022-11-18T07:14:15","modified_gmt":"2022-11-18T07:14:15","slug":"remove-all-occurrences-of-duplicates-from-a-sorted-linked-list-2","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/remove-all-occurrences-of-duplicates-from-a-sorted-linked-list-2\/","title":{"rendered":"Remove all occurrences of duplicates from a sorted linked list."},"content":{"rendered":"

\"\"<\/p>\n

We have observed that a linked list might contain elements which repeat themselves in the list. So, now we will look into a program to remove all occurrences of duplicates from a sorted linked list\n <\/p>\n

Problem Statement to remove all occurrences of duplicates from a sorted linked list<\/h3>\n

In this question, we are given a sorted Singly Linked List. We have to remove all the occurrences of duplicate nodes in the list.<\/p>\n

Problem Statement Understanding on how to remove all occurrences of duplicates from a sorted linked list<\/h3>\n

Let\u2019s try to understand the problem statement with examples.<\/p>\n

Suppose if the given sorted list is:<\/p>\n

\"\"<\/p>\n

Now, we have to remove all the occurrences of duplicates from this list. As we can see, 39 is the only repeating value (which have more than 1 occurrences in the linked list), so we will delete all the nodes which have the value 39.<\/p>\n

So, the final linked list after deletion:<\/p>\n

\"\"<\/p>\n

If the given sorted list is:<\/p>\n

\"\"<\/p>\n

Now, as we can see that 2 and 3 are the only repeating values in the linked list (which have more than 1 occurrences in the linked list) so we will have to remove all the occurrences of 2 and 3 from this list. <\/p>\n

So, the final linked list after deletion:<\/p>\n

\"\"<\/p>\n

Explanation:<\/strong> All the nodes which appear more than once have been deleted from the input linked list. The only nodes which appear exactly once in the list remain in the list.<\/p>\n

This question is not a very complex one. We have to make use of list traversal in the question. Let us have a glance at the approach.<\/p>\n

Before moving to the approach, just try to think how you can solve this problem?<\/p>\n

Approach on how to remove all occurrences of duplicates from a sorted linked list<\/h3>\n

The approach is going to be pretty simple. We will maintain a previous pointer which will point to the node just previous to the block of nodes for which we will check for the duplicates, i.e. the previous pointer will point to the last node which has no duplicate.<\/p>\n

As long as we will keep finding duplicates, we will keep traversing through the list. As soon as the duplicates end, we will make the previous pointer point to the next of the last duplicate node of that block. Let us have a look at the algorithm.<\/p>\n

Algorithm for how to remove all occurrences of duplicates from a sorted linked list<\/h3>\n
    \n
  • Create a node dummy which will point to the head of the list, and another node previous which will point to the last node which has no duplicate (initially previous will be pointing to dummy).<\/li>\n
  • Create another node that will be used to traverse through the list. Let us call this node current.<\/li>\n
  • Traverse using current till the end of the list.<\/li>\n
  • Now, as long as the data of next of previous is equal to the data of next of current, increment current by 1.<\/li>\n
  • If the current stays the same, i.e. no duplicate in the current block, then previous = previous – > next<\/strong>. By doing this, we are just incrementing the previous.<\/li>\n
  • Else, there are duplicates, so, previous – > next = current – > next<\/strong>. The reason for doing this is that the previous is pointing to the last node which has no duplicates, and the current has been increased, which means there are duplicates. So, we will make the previous point to the next of current in order to remove the duplicates.<\/li>\n
  • Increment current by one.<\/li>\n
  • After the traversal, make head point to the next of the dummy node.<\/li>\n<\/ul>\n

    Dry Run on how to remove all occurrences of duplicates from a sorted linked list<\/h3>\n

    \"\"<\/p>\n

    Code Implementation<\/h3>\n\t\t\t\t\t\t