# Remove Duplicates In A Sorted Linked List #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a partially written LinkedList class.2. You are required to complete the body of removeDuplicates function. The function is called on a sorted list. The function must remove all duplicates from the list in linear time and constant space3. Input and Output is managed for you. `
Input Format
`Input is managed for you`
Output Format
`Output is managed for you`
Question Video
Constraints
`1. Time complexity -> O(n)2. Space complexity -> constant`
Sample Input
`102 2 2 3 3 5 5 5 5 5`
Sample Output
`2 2 2 3 3 5 5 5 5 5 2 3 5 `

• Editorial

The problem deals with removing duplicate elements in a sorted linked list. For example, we have a list 1 -> 2 -> 2 -> 2 -> 3 -> 4 -> 5 -> 5, then the output list should be 1 -> 2 -> 3 -> 4 -> 5.

The idea here is to check for every element whether it is already present in the list or not and then making a selection for the same. As here we know that the list is sorted so checking the lastmost element can make us ensure that whether the list contains the current element or not.To achieve this we are going to create our new list, where we will store our output list. Now we will run a loop up to the point when our list becomes empty and for every iteration, we will select the first node and remove it from the list. Now in our output list, we would check whether the element is already present in the list or not, if present then we would discard it else we would add that element to the list.

Below is the implementation in Java:

```public void removeDuplicates(){
while(this.size() > 0){
int val = this.getFirst();
this.removeFirst();
if(res.size() == 0 || val != res.tail.data){
}
}
this.tail = res.tail;
this.size = res.size;
}```

java false

Dry Run

Input List: 1 -> 2 -> 2 -> 2 -> 3 -> 4 -> 5 -> 5

Output List: 1 -> 2 -> 3 -> 4 -> 5

Initially, res is an empty list (which will store our output result)

this is a pointer pointing to our input linked list.

First Iteration

this.size() = 8 > 0

val= 2

removeFirst()

As res.size() == 0 therefore, res.add(1)

List: 2 -> 2 -> 2 -> 3 -> 4 -> 5 -> 5

Res: 1

Second Iteration

this.size() = 7> 0

val= 2

removeFirst()

As val!=res.tail.data (= 1), therefore, res.add(2)

List: 2 -> 2 -> 3 -> 4 -> 5 -> 5

Res: 1 -> 2

Third Iteration

this.size() = 6> 0

val= 2

removeFirst()

As val==res.tail.data (= 2), hence no updation

List: 2 -> 3 -> 4 -> 5 -> 5

Res: 1 -> 2

Fourth Iteration

this.size() = 5> 0

val= 2

removeFirst()

As val==res.tail.data (= 2), hence no updation

List: 3 -> 4 -> 5 -> 5

Res: 1 -> 2

Fifth Iteration

this.size() = 4> 0

val= 3

removeFirst()

As val!=res.tail.data (= 2), therefore res.add(3)

List: 4 -> 5 -> 5

Res: 1 -> 2 -> 3

Sixth Iteration

this.size() = 3> 0

val= 4

removeFirst()

As val!=res.tail.data (= 3), therefore res.add(4)

List: 5 -> 5

Res: 1 -> 2 -> 3 -> 4

Seventh Iteration

this.size() = 2> 0

val= 5

removeFirst()

As val!=res.tail.data (= 4), therefore res.add(5)

List: 5

Res: 1 -> 2 -> 3 -> 4 -> 5

Eight Iteration

this.size() = 1> 0

val= 5

removeFirst()

As val==res.tail.data (= 5), hence no updation

List: null

Res: 1 -> 2 -> 3 -> 4 -> 5

Ninth Iteration

this.size() = 0

loop breaks.

Output List: 1 -> 2 -> 3 -> 4 -> 5

Hence our algorithm is verified.

Time Complexity: O(n)

The time complexity for the function is linear as we are traversing on every node and updating the res list which is dependent on the length of the linked list.

Space Complexity: O(n)

The space complexity for the function is linear as we have created an output list for storing the resultant list.

• Related Topics

Run

Run
Id Name