Dada una lista enlazada, encuentre su primer elemento entero no repetido.
Ejemplos:
C++
// C++ program to find first non-repeating
// element in a linked list
#include<bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
/* Function to find the first non-repeating
element in the linked list */
int firstNonRepeating(struct Node *head)
{
// Create an empty map and insert all linked
// list elements into hash table
unordered_map<int, int> mp;
for (Node *temp=head; temp!=NULL; temp=temp->next)
mp[temp->data]++;
// Traverse the linked list again and return
// the first node whose count is 1
for (Node *temp=head; temp!=NULL; temp=temp->next)
if (mp[temp->data] == 1)
return temp->data;
return -1;
}
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main()
{
// Let us create below linked list.
// 85->15->18->20->85->35->4->20->NULL
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 35);
push(&head, 85);
push(&head, 20);
push(&head, 18);
push(&head, 15);
push(&head, 85);
cout << firstNonRepeating(head);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// Java program to find first non-repeating
// element in a linked list
/* Link list node */
static class Node
{
public int data;
public Node next;
public Node(){
this.data = 0;
this.next = null;
}
public Node(int data,Node next){
this.data = data;
this.next = next;
}
};
/* Function to find the first non-repeating
element in the linked list */
static int firstNonRepeating(Node head)
{
// Create an empty map and insert all linked
// list elements into hash table
HashMap<Integer,Integer> mp = new HashMap<>();
for (Node temp=head; temp != null; temp = temp.next){
if(mp.containsKey(temp.data)){
mp.put(temp.data,mp.get(temp.data)+1);
}
else{
mp.put(temp.data,1);
}
}
// Traverse the linked list again and return
// the first node whose count is 1
for (Node temp=head; temp!=null; temp=temp.next){
if (mp.get(temp.data) == 1)
return temp.data;
}
return -1;
}
/* Function to push a node */
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
/* Driver program to test above function*/
public static void main(String args[])
{
// Let us create below linked list.
// 85->15->18->20->85->35->4->20->NULL
Node head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 35);
head = push(head, 85);
head = push(head, 20);
head = push(head, 18);
head = push(head, 15);
head = push(head, 85);
System.out.print(firstNonRepeating(head));
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 program to find first non-repeating # element in a linked list # Link list node class Node: def __init__(self, data): self.data = data self.next = None # Function to find the first non-repeating # element in the linked list def firstNonRepeating(head): # Create an empty map and insert all linked # list elements into hash table mp = dict() temp = head while (temp != None): if temp.data not in mp: mp[temp.data] = 0 mp[temp.data] += 1 temp = temp.next temp = head # Traverse the linked list again and return # the first node whose count is 1 while (temp != None): if temp.data in mp: if mp[temp.data] == 1: return temp.data temp = temp.next return -1 # Function to push a node def push(head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref # Driver code if __name__=='__main__': # Let us create below linked list. # 85->15->18->20->85->35->4->20->NULL head = None head = push(head, 20) head = push(head, 4) head = push(head, 35) head = push(head, 85) head = push(head, 20) head = push(head, 18) head = push(head, 15) head = push(head, 85) print(firstNonRepeating(head)) # This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find first non-repeating
// element in a linked list
/* Link list node */
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
/* Function to find the first non-repeating
element in the linked list */
function firstNonRepeating(head)
{
// Create an empty map and insert all linked
// list elements into hash table
var mp = new Map();
for (var temp=head; temp!=null; temp=temp.next)
{
if(mp.has(temp.data))
{
mp.set(temp.data , mp.get(temp.data)+1)
}
else
{
mp.set(temp.data, 1)
}
}
// Traverse the linked list again and return
// the first node whose count is 1
for (var temp=head; temp!=null; temp=temp.next)
if (mp.get(temp.data) == 1)
return temp.data;
return -1;
}
/* Function to push a node */
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
/* Driver program to test above function*/
// Let us create below linked list.
// 85.15.18.20.85.35.4.20.null
var head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 35);
head = push(head, 85);
head = push(head, 20);
head = push(head, 18);
head = push(head, 15);
head = push(head, 85);
document.write( firstNonRepeating(head));
</script>
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA