Remove Identical From LL

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in company
Adobe

Problem statement

You are preparing for adobe interviews. You came across a problem where you have a sorted linked list of ‘N’ integers. Remove all the occurrences of identical integers from the linked list such that it contains only distinct integers in sorted order.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, the number of test cases.

The first line of each test case contains the linked list separated by space and terminated by -1.
Output Format : 
For each test case, print the updated linked list.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 3*10^3

Where ‘N’ is the number of nodes in the linked list.    

Time Limit : 1 sec
Sample Input 1 :
2
1 3 3 3 4 4 5 -1
1 3 4 4 -1
Sample Output 1 :
1 5
1 3
Explanation For Sample Input 1 :
For first test case :

3 and 4 are repeating in the linked list. So, after removing them from the linked list our resultant linked list becomes : 1 5


For second test case :

4 is repeating in the linked list. So, after removing them from the linked list our resultant linked list becomes : 1 3
Sample Input 2 :
2
1 3 4 5 -1
1 2 2 -1
Sample Output 2 :
1 3 4 5
1
Hint

Try to traverse the linked list recursively while checking adjacent numbers.

Approaches (2)
Recursive approach

The basic idea is to traverse the linked list recursively. While traversing, we check the adjacent nodes and remove the nodes if they are equal. Else, we traverse further in the linked list.

 

Here is the algorithm :
 

  1. Base case :
    • If ‘HEAD’ is equal to ‘NULL’ or next of ‘HEAD’ is equal to ‘NULL’.
      • Return ‘HEAD’.
  2. Check if the value at ‘HEAD’ is equal to the value next to ‘HEAD’. (Check condition)
    • Run a loop till the next of ‘HEAD’ is not equal to ‘NULL’ and the value of ‘HEAD’ is equal to the value of the node next to ‘HEAD’.
      • Update ‘HEAD’ to next of ‘HEAD’.  (Removing nodes)
    • Recursively call the function on the node next to ‘HEAD’ and return it.
  3. Else
    • Recursively call the function on the node next to ‘HEAD’ and update the next of ‘HEAD’ with it.
    • Return ‘HEAD’.
Time Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

We traverse the whole linked list recursively to check the adjacent numbers. Therefore, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the linked list.

 

The recursive stack can contain the length of the linked list. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Remove Identical From LL
Full screen
Console