C++ 中链表中的第一个非重复项
c++server side programmingprogramming更新于 2025/5/31 8:37:17
在这个问题中，我们给出了一个大小为 N 的链表 LL。我们的任务是创建一个程序来查找链表中的非重复项。
链表是一系列数据结构，它们通过链接连接在一起。
让我们举一个例子来理解这个问题，
输入:LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5 输出:1
解释 −
出现频率为 1 和 6 的元素。其中 1 在链接列表中首先出现。
解决方法
解决问题的方法是创建一个哈希表，用于存储元素及其出现频率。要找到链接列表中的第一个非重复值，我们将遍历链接列表并将哈希图中不存在的元素插入其中，初始出现频率为 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<<"链表的第一个非重复元素是 "<<findFirstNonRepLL(head);
return 0;
}
输出
链表的第一个非重复元素是 1
