数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中链表中第一个不重复的元素
在这个问题中，我们给定一个大小为 N 的链表 LL。我们的任务是创建一个程序来查找链表中不重复的元素。
链表是由数据结构组成的序列，这些数据结构通过链接连接在一起。
让我们举个例子来理解这个问题，
Input: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5 Output: 1
说明 -
The elements with a single occurrence frequency are 1 and 6. Out of these 1 occurred first in the linked list.
解决方案方法
解决此问题的一种方法是创建一个哈希表，该表将存储元素及其出现的频率。为了找到链表中第一个不重复的值，我们将遍历链表并将哈希映射中不存在的元素插入到哈希映射中，初始出现频率为 1。如果哈希映射中存在任何元素，则增加其出现频率。遍历链表后，我们将检查哈希映射中出现频率为 1 的值，并返回遇到的第一个值。
示例
程序说明我们解决方案的工作原理
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* next;
};
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;
}
int findFirstNonRepLL(struct Node *head){
unordered_map<int, int> freqMap;
for (Node *temp=head; temp!=NULL; temp=temp->next){
freqMap[temp->data]++;
}
for (Node *temp=head; temp!=NULL; temp=temp->next){
if (freqMap[temp->data] == 1){
return temp->data;
}
}
return -1;
}
int main(){
struct Node* head = NULL;
push(&head, 5);
push(&head, 6);
push(&head, 2);
push(&head, 1);
push(&head, 4);
push(&head, 2);
push(&head, 6);
push(&head, 4);
cout<<"The first non repeating element of the linked list is "<<findFirstNonRepLL(head);
return 0;
}输出
The first non repeating element of the linked list is 1
更新时间： 2022-02-01
170 次浏览
广告