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 space
3. 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
10
2 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(){
                                        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






Video Solution

Code Solution

Run
 
Run
Id Name