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

Happy Coding! Enjoy Algorithms!!