Remove duplicates from a sorted linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a sorted LinkedList and are asked to remove the duplicate elements present in the list.

Problem Statement Understanding

According to the problem statement, we will be given a sorted linked list that may contain duplicate elements. We need to remove the duplicate elements from the list.

Let's try to understand the problem with the help of some examples.

If the given input sorted linked list is:

  • As we can see in the above list, there are multiple occurrences of elements 10, 12 in the linked list.
  • So it means that the list contains duplicates of 10, 12 , and we need to remove these duplicates from the linked list.
  • After removing the duplicate elements from the list, the output linked list will be:

If the linked list is: head->11->11->25->40->40->45.

  • In this case, as we can see in the above list, 11 and 40 are duplicate elements present more than once in the list.
  • After removing the duplicate elements from the list, the output will be head->11->25->40->45.
Some more examples:

Sample Input 1: head->2->2->3->4->7.
Sample Output 1: head->2->3->4->7.

Sample Input 2: head->3->3->7->7->7->11->11->12->15.
Sample Input 2: head->3->7->11->12->15.

Now, I think from the above examples, the problem statement is clear. So let's see how we will approach it.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.

Let’s move to the approach section.

Approach 1 (Using Hashmaps)

Our approach will be simple; we will be using hashmap:

  • While traversing the Linked List, for every element, we will check if it is already present in the map or not.
    • If it is already present, then we will remove the element from the list.
    • Else we will push the element in the hash map and move forward.

This approach will require extra space.

Time complexity: O(n), where n is the number of nodes in the linked list.
Space complexity: O(n), where n is the number of nodes in the linked list.

Although the above approach will work fine, but it requires some extra space. Now the main question is do we necessarily need this extra space? Can we remove duplicates from the sorted linked list without consuming extra space?

  • Let's see in the next section how we can solve this problem without using extra space.

Let's move to the next approach.

Approach 2 (Using two pointers)

Our approach will be straightforward:

  • We will create a pointer prev that will to the first occurrence of the element and second pointer temp to traverse the linked list.
  • If the value of the temp pointer is equal to the prev pointer, temp will move forward and when we find the node whose value is not equal to prev pointer, we will connect the node pointer by prev with the node pointed by temp and move prev pointer to the position of temp and move temp forward.

From the above approach, we can see that we are using constant extra space here.

Time complexity: O(n), where n is the number of nodes in the linked list.
Space complexity: O(1), As constant extra space, is required.

Let's see another approach that solves this problem in similar time and space complexity using two pointers for the sake of learning.

Approach 3

The idea is very simple:

  • Traverse the list using a pointer, say current.
  • While traversing the list compare the current node's value with the value of it's next node.
    • If they are the same, remove the next node.
    • Else move forward.
  • Keep on doing this till we reach the end of the linked list.

Algorithm

  • Create a pointer current.
  • Traverse the Linked List in a linear fashion.
  • For every node, check the next node's data.
    • If they are the same, then delete the current's next node by changing the current node pointer.
    • If they are different, then move current pointer forward (current = current->next).
  • Keep on doing this untill current->next != NULL or we can say untill we reach the end of the linked list.

Dry Run


Code Implementation

#include 
using namespace std;

/* Node structure of the linked list nodes */
class Node{
	public:
	int data;
	Node* next;
};

/* Using this function we will be removing the duplicates elements from the given sorted linked list */
void removeDuplicatesSortedList(Node* head){
	Node* current = head;
	Node* next_next;
	if (current == NULL)
	return;
	while (current->next != NULL){
		if (current->data == current->next->data){
			next_next = current->next->next;
			free(current->next); 
			current->next = next_next;
		}
		else{
			current = current->next;
		}
	}
}

/* Using this function we will be pushing a new node at the head of the linked list */
void pushNodeHead(Node** head, int data){
	Node* new_node = new Node();
	new_node->data = data;
	new_node->next = (*head);	
	(*head) = new_node;
}

/* Using this function we will be printing the linked list */
void printingLinkedList(Node *node){
	while (node!=NULL){
		cout<<" "<data;
		node = node->next;
	}
	cout<

						 

Output

Linked list before removing duplicates
10 10 10 12 30 35
Linked list after removing duplicates
10 12 30 35

Time Complexity: O(n), single traversal of the list require O(n) time, where n is the number of nodes in the linked list.

In this blog, we have seen how to remove duplicate elements from a sorted single LinkedList in linear time and haven’t used extra space too. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can checkout Prepbytes (Linked List).

Previous post Remove duplicates from an unsorted linked list
Next post An interesting method to print the reverse of a linked list.

Leave a Reply

Your email address will not be published. Required fields are marked *