Remove Duplicates In A Sorted Linked List
1. You are given a partially written LinkedList class.Input Format
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 space
3. Input and Output is managed for you.
Input is managed for youOutput Format
Output is managed for youQuestion Video
1. Time complexity -> O(n)Sample Input
2. Space complexity -> constant
10Sample Output
2 2 2 3 3 5 5 5 5 5
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(){ LinkedList res = new LinkedList(); while(this.size() > 0){ int val = this.getFirst(); this.removeFirst(); if(res.size() == 0 || val != res.tail.data){ res.addLast(val); } } this.head = res.head; 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.
Updating data member linked list with local res linked list.
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.
-
Asked in Companies
-
Related Topics
