Remove Duplicates in a Sorted Linked List-Interview Problem



Difficulty: Medium
Asked in: Myntra, Oracle, Visa, Adobe

Understanding the Problem

Problem Description: Given a sorted linked list which has some duplicate elements, your task is to remove all the duplicate elements from the given Linked List. As a result of solving this problem, your Linked List will only have all unique elements.
For example:
Input:  2->3->3->4->5->7->7->9->NULL
Output: 2->3->4->5->7->9->NULL
Explanation: All the duplicate elements have been removed.
Similarly,
Input: 4->7->9->9->10->11->11->NULL
Output: 4->7->9->10->11->NULL
Possible follow-up questions to ask the interviewer: →
  • Can we modify the given Linked List or have to create a new Linked List? (Ans: You have to modify the same Linked List)

Solutions

We are going to discuss two possible ways to solve this problem: →
  • Iterative Solution: Here we will use simple iteration to iterate through the nodes and delete(remove) duplicate nodes from the given Linked List.
  • Recursive Solution: In this solution, we will use recursion to achieve having only unique elements in our Linked List.

Approach 1: Iterative Solution

Solution idea
In this approach, we will iteratively traverse the entire Linked List. Going to each node one by one, we will compare that node with the adjacent node. If the data value for both the nodes are the same it means that the node is duplicate. We will then de-link one of the duplicate nodes and will follow the same procedure for the rest of the nodes.
Solution steps
  • We will store the value of the head(start) node into another variable say current.
  • We will keep iterating through the linked list until we reach the end node.
  • If there is a match of data values between a node and an adjacent node we will detach one of the nodes by saving its neighbour node’s address into the NextNode variable.
  • We will then delete that duplicate node and attach the previous node of the deleted duplicate node with NextNode.
  • We will keep doing the same for all duplicate nodes if encountered.
Pseudo-code
ListNode removeDuplicatedFromLL(ListNode head)
{
     ListNode current = head;
        
     while(current!=NULL && current.next!=NULL)
     {
         ListNode NextNode = NULL;
         if(current.data == current.next.data)
         {
             NextNode = current.next.next
             delete current.next;  
             current.next = NextNode;
         }
         else
             current = current.next
     }
}
Complexity Analysis
Time Complexity: O(N), where N is the size of the array.
Space Complexity: O(1)(Why?)
Critical ideas to think!
  • Do you think removing duplicates from Linked List is simpler than that from an array? Why or Why not?

Approach 2: Recursive Solution

Solution idea
Here also the basic approach is completely the same, the only difference is in the implementation. The above solution is implemented by using an iterative solution, in this, we will make a recursive solution. For a recursive solution, we need to think about the base condition, an easy operation for us to do and the sub-task that we will leave on recursion. The operation is to compare two nodes and to see if the data values are the same or not.
Solution steps
  • We will decide upon the base case, the base case will be when there is only one node or there is no node at all.
  • We will perform our small task of comparing the head node with its adjacent node.
  • We will perform the necessary things based on the condition. If the nodes match we will save the neighbor’s address and delete the duplicate node.
  • We will recursively call for the rest of the nodes and leave the sub-tasks on recursion.
Pseudo-code
void removeDuplicatesFromLL(ListNode head)
{
    if(head==NULL or head.next==NULL)
       return
    if(head.data == head.next.data)
    {
        ListNode NextNode = head.next.next
        delete head.next
        head.next = NextNode
        removeDuplicatesFromLL(head)
   }
    else
        removeDuplicatesFromLL(head.next)
}
Complexity Analysis
Time Complexity: O(N)
Space Complexity: O(N)

Comparison of Different Solutions

Suggested Problems to Solve

  • Find the most frequent character in a sentence
  • Remove elements to make array sorted
  • Remove duplicates from an unsorted array using Map
  • Remove duplicate elements from a linked list and also the size of the linked list after removing those duplicates












































Comments

Post a Comment

Popular posts from this blog

[13 Feb 2020] Check if a given sequence of moves for a robot is circular or not

Check if a given sequence of moves for a robot is circular or not Link:  https://www.youtube.com/watch?v=f7Zd8hEbCz0 Given a sequence of moves for a robot, check if the sequence is circular or not. A sequence of moves is circular if first and last positions of robot are same. A move can be on of the following. G - Go one unit L - Turn left R - Turn right Input: path[] = "GLGLGLG" Output: Given sequence of moves is circular Input: path[] = "GLLG" Output: Given sequence of moves is circular The idea is to consider the starting position as (0, 0) and direction as East (We can pick any values for these). If after the given sequence of moves, we come back to (0, 0), then given sequence is circular, otherwise not. N | | W -------------- E | | S The move ‘G’ changes either x or y according to following rules. a) If current direction is North, then ‘G’ increments y and doesn’t cha...
Read more

[16 Feb 2020] Given an array where every element occurs three times, except one element which occurs only once.

Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. Examples : Input: arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3} Output: 2 In the given array all element appear three times except 2 which appears once. Input: arr[] = {10, 20, 10, 30, 10, 30, 30} Output: 20 In the given array all element appear three times except 20 which appears once. Following is another O(n) time complexity and O(1) extra space method suggested by aj. We can sum the bits in same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with single occurrence. Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000 Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0; Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0; Sum of...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more