给定一个链表，其中包含一些从1到n的随机整数，其中有许多重复项。将链表中存在的每个重复元素替换为值n+1、n+2、n+3等（在给定链表中从左到右开始）。
null
例如：
Input : 1 3 1 4 4 2 1Output : 1 3 5 4 6 2 7Replace 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 2Output : 1 5 6 4 3 2 7
方法： 1.遍历链表，将链表中出现的每个数字的频率存储在地图中，并与之一起找到链表中出现的最大整数，即。 maxNum . 2.现在，再次遍历链表，如果任何数字的频率大于1，则在第一次出现时将其值设置为-1。 3.这样做的原因是，在下一次出现这个数字时，我们会找到它的值-1，这意味着这个数字以前出现过，用maxNum+1和增量maxNum更改它的数据。
下面是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 Node struct Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } // Function to replace duplicates from a // linked list void 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 given linked 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" ; printList(head); replaceDuplicates(head); cout << "Linked list after replacing" << " duplicates" ; 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" ); printList(head); replaceDuplicates(head); System.out.println( "Linked list after replacing" + " duplicates" ); 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 Node def newNode(data): temp = Node(data) return temp # Function to replace duplicates from a # linked list def 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 list def printList(node): while (node ! = None ): print (node.data, end = ' ' ) node = node. next print () # Driver code if __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 list static 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( "Linked list after" + " replacing duplicates" ); printList(head); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript implementation of the approach // Representation of node class Node { constructor(d) { this .data = d; this .next = null ; } } // Function to insert a node at the beginning function 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 list function 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 list function 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> |
输出：
Linked list before replacing duplicates1 3 1 4 4 2 1 Linked list after replacing duplicates1 3 5 4 6 2 7
本文由 切哈维 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
