Given a linked list that contains some random integers from 1 to n with many duplicates. Replace each duplicate element that is present in the linked list with the values n+1, n+2, n+3 and so on(starting from left to right in the given linked list).
Examples:
Input : 1 3 1 4 4 2 1
Output : 1 3 5 4 6 2 7
Replace 2nd occurrence of 1 with 5 i.e. (4+1)
2nd occurrence of 4 with 6 i.e. (4+2)
3rd occurrence of 1 with 7 i.e. (4+3)
Input : 1 1 1 4 3 2 2
Output : 1 5 6 4 3 2 7
Approach :
- Traverse the linked list, store the frequencies of every number present in linked list in a map and alongwith it find the maximum integer present in linked list i.e. maxNum.
- Now, traverse the linked list again and if the frequency of any number is more than 1, set its value to -1 in map on its first occurrence.
- he reason for this is that on next occurrence of this number we will find its value -1 which means this number has occurred before, change its data with maxNum + 1 and increment maxNum.
Below is the implementation of idea.
C++
// C++ implementation of the approach #include <bits/stdc++.h>using namespace std;/* A linked list node */struct Node { int data; struct Node* next;};// Utility function to create a new Nodestruct Node* newNode(int data){ Node* temp = new Node; temp->data = data; temp->next = NULL; return temp;}// Function to replace duplicates from a // linked listvoid replaceDuplicates(struct Node* head){ // map to store the frequency of numbers unordered_map<int, int> mymap; Node* temp = head; // variable to store the maximum number // in linked list int maxNum = 0; // traverse the linked list to store // the frequency of every number and // find the maximum integer while (temp) { mymap[temp->data]++; if (maxNum < temp->data) maxNum = temp->data; temp = temp->next; } // Traverse again the linked list while (head) { // Mark the node with frequency more // than 1 so that we can change the // 2nd occurrence of that number if (mymap[head->data] > 1) mymap[head->data] = -1; // -1 means number has occurred // before change its value else if (mymap[head->data] == -1) head->data = ++maxNum; head = head->next; }}/* Function to print nodes in a givenlinked list */void printList(struct Node* node){ while (node != NULL) { printf("%d ", node->data); node = node->next; } cout << endl;}/* Driver program to test above function */int main(){ /* The constructed linked list is: 1->3->1->4->4->2->1*/ struct Node* head = newNode(1); head->next = newNode(3); head->next->next = newNode(1); head->next->next->next = newNode(4); head->next->next->next->next = newNode(4); head->next->next->next->next-> next = newNode(2); head->next->next->next->next-> next->next = newNode(1); cout << "Linked list before replacing" << " duplicates\n"; printList(head); replaceDuplicates(head); cout << "Linked list after replacing" << " duplicates\n"; printList(head); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GFG{ // Representation of node static class Node { int data; Node next; Node(int d) { data = d; next = null; }}; // Function to insert a node at the beginning static Node insert(Node head, int item) { Node temp = new Node(0); temp.data = item; temp.next = head; head = temp; return head;} // Function to replace duplicates from a // linked list static void replaceDuplicates( Node head) { // map to store the frequency of numbers Map<Integer, Integer> mymap = new HashMap<>(); Node temp = head; // variable to store the maximum number // in linked list int maxNum = 0; // traverse the linked list to store // the frequency of every number and // find the maximum integer while (temp != null) { mymap.put(temp.data,(mymap.get(temp.data) == null?0:mymap.get(temp.data))+1); if (maxNum < temp.data) maxNum = temp.data; temp = temp.next; } // Traverse again the linked list while (head != null) { // Mark the node with frequency more // than 1 so that we can change the // 2nd occurrence of that number if (mymap.get(head.data) > 1) mymap.put(head.data, -1); // -1 means number has occurred // before change its value else if (mymap.get(head.data) == -1) head.data = ++maxNum; head = head.next; } } // Function to print nodes in a given //linked list /static void printList( Node node) { while (node != null) { System.out.printf("%d ", node.data); node = node.next; } System.out.println();} // Driver code public static void main(String args[]){ // The constructed linked list is: // 1->3->1->4->4->2->1/ Node head = new Node(1); head.next = new Node(3); head.next.next = new Node(1); head.next.next.next = new Node(4); head.next.next.next.next = new Node(4); head.next.next.next.next. next = new Node(2); head.next.next.next.next. next.next = new Node(1); System.out.println( "Linked list before replacing" + " duplicates\n"); printList(head); replaceDuplicates(head); System.out.println("Linked list after replacing" + " duplicates\n"); printList(head); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach # A linked list node class Node: def __init__(self, data): self.data = data self.next = None# Utility function to create a new Nodedef newNode(data): temp = Node(data) return temp # Function to replace duplicates from a # linked listdef replaceDuplicates(head): # Map to store the frequency of numbers mymap = dict() temp = head # Variable to store the maximum number # in linked list maxNum = 0 # Traverse the linked list to store # the frequency of every number and # find the maximum integer while (temp): if temp.data not in mymap: mymap[temp.data] = 0 mymap[temp.data] += 1 if (maxNum < temp.data): maxNum = temp.data temp = temp.next # Traverse again the linked list while (head): # Mark the node with frequency more # than 1 so that we can change the # 2nd occurrence of that number if (mymap[head.data] > 1): mymap[head.data] = -1 # -1 means number has occurred # before change its value elif (mymap[head.data] == -1): maxNum += 1 head.data = maxNum head = head.next # Function to print nodes in a given# linked listdef printList(node): while (node != None): print(node.data, end = ' ') node = node.next print() # Driver codeif __name__=='__main__': # The constructed linked list is: # 1.3.1.4.4.2.1 head = newNode(1) head.next = newNode(3) head.next.next = newNode(1) head.next.next.next = newNode(4) head.next.next.next.next = newNode(4) head.next.next.next.next.next = newNode(2) head.next.next.next.next.next.next = newNode(1) print("Linked list before replacing duplicates") printList(head) replaceDuplicates(head) print("Linked list after replacing duplicates") printList(head)# This code is contributed by rutvik_56 |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG{ // Representation of node class Node { public int data; public Node next; public Node(int d) { data = d; next = null; }}; // Function to insert a node at the beginning static Node insert(Node head, int item) { Node temp = new Node(0); temp.data = item; temp.next = head; head = temp; return head;} // Function to replace duplicates from a // linked list static void replaceDuplicates( Node head) { // map to store the frequency of numbers Dictionary<int, int> mymap = new Dictionary<int, int>(); Node temp = head; // variable to store the maximum number // in linked list int maxNum = 0; // traverse the linked list to store // the frequency of every number and // find the maximum integer while (temp != null) { if(mymap.ContainsKey(temp.data)) mymap[temp.data] = mymap[temp.data] + 1; else mymap.Add(temp.data, 1); if (maxNum < temp.data) maxNum = temp.data; temp = temp.next; } // Traverse again the linked list while (head != null) { // Mark the node with frequency more // than 1 so that we can change the // 2nd occurrence of that number if (mymap[head.data] > 1) mymap[head.data] = -1; // -1 means number has occurred // before change its value else if (mymap[head.data] == -1) head.data = ++maxNum; head = head.next; } } // Function to print nodes in a given // linked liststatic void printList( Node node) { while (node != null) { Console.Write("{0} ", node.data); node = node.next; } } // Driver code public static void Main(String []args){ // The constructed linked list is: // 1->3->1->4->4->2->1/ Node head = new Node(1); head.next = new Node(3); head.next.next = new Node(1); head.next.next.next = new Node(4); head.next.next.next.next = new Node(4); head.next.next.next.next.next = new Node(2); head.next.next.next.next.next.next = new Node(1); Console.WriteLine("Linked list before" + " replacing duplicates"); printList(head); replaceDuplicates(head); Console.WriteLine("\nLinked list after" + " replacing duplicates"); printList(head); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach// Representation of nodeclass Node { constructor(d) { this.data = d; this.next = null; }}// Function to insert a node at the beginningfunction insert(head, item) { var temp = new Node(0); temp.data = item; temp.next = head; head = temp; return head;}// Function to replace duplicates from a// linked listfunction replaceDuplicates(head) { // Map to store the frequency of numbers var mymap = {}; var temp = head; // Variable to store the maximum number // in linked list var maxNum = 0; // Traverse the linked list to store // the frequency of every number and // find the maximum integer while (temp != null) { if (mymap.hasOwnProperty(temp.data)) mymap[temp.data] = mymap[temp.data] + 1; else mymap[temp.data] = 1; if (maxNum < temp.data) maxNum = temp.data; temp = temp.next; } // Traverse again the linked list while (head != null) { // Mark the node with frequency more // than 1 so that we can change the // 2nd occurrence of that number if (mymap[head.data] > 1) mymap[head.data] = -1; // -1 means number has occurred // before change its value else if (mymap[head.data] == -1) head.data = ++maxNum; head = head.next; }}// Function to print nodes in a given// linked listfunction printList(node){ while (node != null) { document.write(node.data + " "); node = node.next; }}// Driver code// The constructed linked list is:// 1->3->1->4->4->2->1/var head = new Node(1);head.next = new Node(3);head.next.next = new Node(1);head.next.next.next = new Node(4);head.next.next.next.next = new Node(4);head.next.next.next.next.next = new Node(2);head.next.next.next.next.next.next = new Node(1);document.write("Linked list before " + "replacing duplicates <br>");printList(head);replaceDuplicates(head);document.write("<br>Linked list after " + "replacing duplicates <br>");printList(head);// This code is contributed by rdtank</script> |
Output
Linked list before replacing duplicates 1 3 1 4 4 2 1 Linked list after replacing duplicates 1 3 5 4 6 2 7
Time Complexity: O(N)
Auxiliary Space: O(N)
This article is contributed by Chhavi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
