Delete duplicates in sorted linked list
In this blog, we will learn how we can remove duplicates from a sorted linked list. So let's suppose we have a Linked List sorted in increasing order, and it may or may not contain some duplicate nodes. Now we need to remove all the duplicate nodes from this link list. For example- Show
There are numerous approaches to doing the above task, as we can travel through the linked list by comparing the current node with its next node and removing the next node if it is equal. Or we can also use a two-pointer approach where the first pointer helps us traverse through the linked list, and the second pointer only points to the distinct nodes in the list. Another approach could be to use an unordered map to store all the nodes, and as maps don't allow duplicates, thus we will get rid of all the duplicates. So let's see all of these methods one by one; start with the simple traversal-based approach. Recommended: Before stepping on to the solution, try it by yourself on CodeStudio. Approach 1: NaiveThe naive approach to solve this problem is to iterate through the linked list and keep comparing the current node with its next node, and if they are the same, delete the next node and move to the next node. Finally, print the linked list. This approach can be implemented using recursion, so let's go through both implementations one by one. Algorithm
Implementation#includeInput 7 5 4 3 2 2 2 1Output Enter the number of nodes in the list- Enter the nodes in the list- 1 2 3 4 5Complexity AnalysisThe time complexity of this approach is- O(N), where N is the number of nodes in the linked list. The space complexity of this approach is- O(1). Recursive implementation of the above approach#includeInput 7 5 4 3 2 2 2 1Output Enter the number of nodes in the list- Enter the nodes in the list- 1 2 3 4 5Complexity AnalysisThe time complexity of this approach is- O(N) The space complexity of this approach is- O(N) Approach 2: Using Two PointersThis approach uses two-pointers to remove duplicates from the sorted linked list. The first pointer iterates through the whole list. And the second pointer moves over only those nodes which are distinct. While iterating through the list, whenever the first pointer encounter duplicate nodes, it skips them, and when it encounters a distinct node, it moves the second pointer from the last distinct node to this new node. Algorithm
Implementation#includeInput 7 5 4 3 2 2 2 1Output Enter the number of nodes in the list- Enter the nodes in the list- 1 2 3 4 5Complexity AnalysisThe time complexity of this approach is- O(N) The space complexity of this approach is- O(1) Approach 3: Using MapsAnother approach to solving this problem is using maps. We traverse through the linked list and check if the node has already occurred or node. If it has not occurred, we print it and mark it as visited on the map. And skip it if it is already visited. Algorithm
Implementation#includeInput 7 5 4 3 2 2 2 1Output Enter the number of nodes in the list- Enter the nodes in the list- 1 2 3 4 5Complexity AnalysisThe time complexity of this approach is- O(N) The space complexity of this approach is- O(1) Frequently Asked QuestionsWhat are the types of the linked list?The linked list is generally of four types- What is the difference between array and linked lists?The array is a contiguous block of elements of similar data types. In contrast, a linked list is a collection of objects called nodes. These nodes contain data and pointers to the next nodes in the linked list. These nodes are not necessarily stored in contiguous memory blocks. What is random access to elements? Is it possible in a linked list?Random access of elements refers to a condition when we can access any element in a collection of elements directly in one step, i.e., in O(1) time. It is possible in an array but not in linked lists. What is the time complexity of insert operation on unordered maps in C++ STL?The insert operation on unordered maps in C++ STL is constant O(1) in average cases and linear O(N) in worst cases. What is the difference between a node in a singly linked list and a doubly-linked list?A node in a singly linked list only contains data and the pointer to the next node, whereas a doubly-linked list contains data and pointers to the next and previous nodes. ConclusionIn this blog, we learned the different approaches used to remove duplicates from the sorted linked list.
More suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more. Refer to the top list of problems of Map data structure. I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the CodeStudio. Enroll in our courses, refer to the test series and problems available, and look at the interview bundle for placement preparations for big tech companies like Amazon, Microsoft, Google, and many more. Do upvote our blogs if you find them helpful and engaging! Happy Learning!! |