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