Last Appearance

Posted: 4 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given an unsorted Singly Linked List with 'N' nodes which may contain duplicate elements. You are supposed to remove all duplicate elements from the linked list and keep only the last appearance of elements.

Input format :
The first line of the input contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
Output format :
Print a single line containing updated list elements separated by a single space.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints :
0 <= N <= 5 * 10^5
-10^9 <= data <= 10^9 and data != -1

Where 'data' is the value of elements that exist in the linked list.

Time limit: 1 sec
Approach 1

One fundamental approach will be to check for whether the current element's data already exists ahead in the given linked list or not? 

 

If the current node's data already exists in the list, then we delete the current node. And we go to the next node. We should care about that; our head of the linked list can also be deleted in such a case when the head's data of the given linked list already contains that element. For such a case, We will make a dummy node, and the next node of the dummy node will point to the head of the linked list.

 

The steps are as follows:-

 

  1. We start with the current node, say ‘CURR’, and our ‘CURR’ keep going till the end of the linked list. Initially, our ‘CURR’ is at the ‘DUMMY’ node.
  2. For each ‘CURR→NEXT’, we will check whether the data of the ‘CURR→NEXT’ node contains in the linked list or not?
    • Let say ‘TEMP’ is a node that is going to check that whether the data of the ‘CUR→NEXT’ node exists or not in a given linked list while traversing in the forward direction from ‘CURR→NEXT→NEXT’ to the end of the linked list.
    • If at any stage, data of ‘TEMP’ is equal to the data of the ‘CURR→NEXT’ node, then we delete the ‘CURR→NEXT’ node with the following steps:
      • Store the ‘CURR→NEXT’ as ‘DUPLICATENODE’.
      • Make ‘CURR→NEXT’ = ‘CURR→NEXT→NEXT’
      • Delete stored node of 'DUPLICATENODE.
    • If none of the data of ‘TEMP’ found is equal to data of ‘CURR→NEXT’ then we will go to the next node of the ‘CURR’ node.
  3. Return head of modified, linked list, i.e., ‘DUMMY→NEXT’.
Try Problem