Không lặp lại đầu tiên trong danh sách liên kết trong C ++

Trong bài toán này, chúng tôi được cung cấp một danh sách liên kết LL có kích thước N. Nhiệm vụ của chúng tôi là tạo chương trình tìm kiếm không lặp lại trong danh sách liên kết .

Danh sách được liên kết là một chuỗi các cấu trúc dữ liệu, được kết nối với nhau thông qua các liên kết.

Hãy lấy một ví dụ để hiểu vấn đề,

Input: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5
Output: 1

Giải thích -

The elements with a single occurrence frequency are 1 and 6. Out of these 1 occurred first in the linked list.

Phương pháp tiếp cận giải pháp

Một cách tiếp cận để giải quyết vấn đề là tạo một bảng băm sẽ lưu trữ các phần tử và tần suất xuất hiện của chúng. Để tìm giá trị không lặp lại đầu tiên trong danh sách được liên kết, chúng tôi sẽ duyệt qua danh sách được liên kết và chèn các phần tử không có trong bản đồ băm vào nó với tần suất xuất hiện ban đầu 1. Nếu bất kỳ phần tử nào có mặt trong bản đồ băm, hãy tăng tần suất xuất hiện của nó tần số. Sau khi duyệt qua danh sách được liên kết, chúng tôi sẽ kiểm tra giá trị trong bản đồ băm có tần suất xuất hiện là một và trả về các giá trị đầu tiên mà chúng gặp phải.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The first non repeating element of the linked list is 1