Last Appearance

Moderate
0/80
Average time to solve is 38m
profile
Contributed by
44 upvotes
Asked in companies
AdobeVisaOracle

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
7 11 13 23 7 11 13 -1
Sample Output 1:
23 7 11 13 -1
Explanation of Sample Input 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.
Sample Input 2:
13 1 19 3 9 -1
Sample Output 2:
13 1 19 3 9 -1
Explanation of Sample Input 2:
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.
Hint

How do you know that data of the current node will appear again in the given list?

Approaches (2)
Brute Force Approach

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’.
Time Complexity

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).

Space Complexity

O(1).

 

We are not using any extra space. So overall, our space complexity will be O(1).

Code Solution
(100% EXP penalty)
Last Appearance
Full screen
Console