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