Last Updated: 9 Sep, 2021

Remove Identical From LL

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 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 :

Base case :
- If ‘HEAD’ is equal to ‘NULL’ or next of ‘HEAD’ is equal to ‘NULL’.
  - Return ‘HEAD’.
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.
Else
- Recursively call the function on the node next to ‘HEAD’ and update the next of ‘HEAD’ with it.
- Return ‘HEAD’.

Solve now

02 Approach

The idea is similar to the previous approach. In this approach, we traverse the linked list iteratively and check for adjacent nodes. We also create a new node and attach it to the starting of the linked list, whose next will be pointing to the ‘HEAD’ node to handle the case when the ‘HEAD’ node itself consists of repeating numbers.

Here is the algorithm :

Create a new node (say, ‘CURR’) and update next of ‘CURR’ to ‘HEAD’.
Create a new node (say, ‘PREV’) and initialize it with ‘CURR’.
Run a loop till ‘HEAD’ is not equal to ‘NULL’.
- Check if the node next to ‘HEAD’ is not equal to NULL and the value at ‘HEAD’ is equal to the value of the node 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)
  - Update next of ‘PREV’ to next of ‘HEAD’.
- Else, update ‘PREV’ to next of ‘PREV’.
- Update ‘HEAD’ to next of ‘HEAD’.
Finally, return the node next to the ‘CURR’.

Solve now