Problem of the day
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.
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.
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
7 11 13 23 7 11 13 -1
23 7 11 13 -1
7, 11, and 13 have appeared two times, so we remove the first appearance of 7, 11, and 13 and keep their last appearance. Since 7, 11 and 13 are removed, so now the head of the modified, linked list becomes 23.
13 1 19 3 9 -1
13 1 19 3 9 -1
There are no duplicate elements in the given linked list, so there will be no elements deleted. And the modified linked list will be the same as the given linked list.
How do you know that data of the current node will appear again in the given list?
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:-
O(N^2), where ‘N’ is the number of nodes in the linked list.
We are pivoting each node at once, and for each node, we are going to check whether the list already containing the data of the pivoted node or not? So there will be ‘N’ node to pivot, and for each node, we are traversing in the list to check for duplicates which cost O(N). So over all time complexity will be O(N^2).
O(1).
We are not using any extra space. So overall, our space complexity will be O(1).