Last Updated: 4 Oct, 2020
Last Appearance
Moderate
Asked in companies
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
Approaches
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:-
- 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.
- 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.
- Return head of modified, linked list, i.e., ‘DUMMY→NEXT’.
In this approach, our idea is to reverse the given linked list. So once we reverse the given linked list, our task will be to remove all the nodes with duplicate data while iterating in the given list in the forward direction. That’s means while traversing in the forward direction in the given list, if we find a node such that data of that node has already visited, then we delete that node. If data of that node has not yet visited then we will mark it as visited and go for the next node. And finally, before returning the answer, we will again reverse our modified list.
The steps are as follows:
- Make a dummy node so that we can handle an empty linked list also. And the next node of the dummy node will store the 'HEAD' of the linked list.
- We are going to use HashSet for storing the data which we have already visited.
- Start with a dummy node say 'CURNODE'. Initially, 'CURNODE' will be pointing to the dummy node.
- For each 'CURNODE', we will get the next node of 'CURNODE' let's say 'NEXTNODE', and check whether the data of 'NEXTNODE' is already visited or not?
- If already visited then we will delete the next node of the ‘CURNODE’ node with the following steps:
- Store the 'NEXTNODE' as 'DUPLICATENODE'.
- Make 'CURNODE→NEXT'='NEXTNODE→NEXT'
- Delete stored node of 'DUPLICATENODE'.
- Else, We will mark data of the ‘NEXTNODE’ as visited and move ‘CURNODE’ to the next node of ‘CURNODE’.
- If already visited then we will delete the next node of the ‘CURNODE’ node with the following steps:
- Before return the answer, we will again reverse the modified, linked list.
- Return the modified ‘HEAD’ of the linked list.