Recognizing the Problem 

Your objective is to remove all duplicate elements from the supplied Linked List, given a sorted linked list with some duplicate elements. As a result of resolving this issue, your Linked List will only contain elements that are unique. 

Consider the following scenario: 

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

Questions to ask the interviewer as a follow-up: 

Is it possible to edit the existing Linked List or do we need to establish a new one? (Answer: You must change the same Linked List.)

Solutions 

We’ll look at two different approaches to solving this issue: 

• Iterative Solution: To iterate through the nodes and delete(remove) duplicate nodes from the given Linked List, we’ll utilise basic iteration. 
• Recursive Approach: In this solution, we will utilise recursion to ensure that our Linked List contains only unique members.

Approach 1: Iterative Solution

Solution idea

We’ll iteratively traverse the complete Linked List with this method. We’ll compare each node to the one next to it as we go through the tree. If the data value for both nodes is the same, the node is considered duplicate. After that, we’ll delink one of the duplicate nodes and repeat the process for the remaining nodes.

Solution steps

• The value of the head(start) node will be saved in another variable called current. 
• We’ll iterate through the linked list until we get to the last node. 
• If the data values of a node and an adjacent node match, we shall detach one of the nodes by saving the address of its neighbour node into the NextNode variable. 
• After that, we’ll delete the duplicate node and attach NextNode to the preceding node of the deleted duplicate node. 
• If duplicate nodes are found, we shall repeat the process.

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?)

Approach 2: Recursive Solution

Solution idea

The essential idea is the same in this case as well; the only difference is in the implementation. We shall develop a recursive solution for the above answer, which will be accomplished using an iterative solution. For a recursive solution, we must consider the base condition, a simple operation, and the sub-task that will be left to recursion. The operation compares two nodes to see if their data values are identical.

Solution steps

• We’ll choose the base case, which will be when there is only one node or none at all. 
• We’ll finish our tiny assignment by comparing the head node to its neighbouring node. 
• We’ll take the required steps based on the situation. We’ll save the neighbor’s address and delete the duplicate node if the nodes match. 
• We’ll call the rest of the nodes recursively 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

Problems to Solve Suggestions 

• Find the most common character in a sentence and remove components to sort the array 
• Using Map, remove duplicates from an unsorted array. 
• Remove duplicate elements from a linked list, as well as the linked list’s size once they’ve been removed. 

Good luck with your coding! Algorithms are fun!!