ไม่ซ้ำครั้งแรกในรายการที่เชื่อมโยงใน C ++

ในปัญหานี้ เราได้รับลิงก์ลิสต์ LL ขนาด N หน้าที่ของเราคือ สร้างโปรแกรมสำหรับค้นหารายการที่ไม่ซ้ำในรายการที่ลิงก์ .

รายการที่เชื่อมโยงคือลำดับของโครงสร้างข้อมูลซึ่งเชื่อมต่อกันผ่านลิงก์

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

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. หากมีองค์ประกอบใดอยู่ในแผนที่แฮช ค่านั้นจะเพิ่มขึ้น ความถี่. หลังจากสำรวจรายการที่เชื่อมโยง เราจะตรวจสอบค่าในแผนที่แฮชที่มีความถี่การเกิดเป็นหนึ่ง และส่งคืนค่าแรกที่พบ

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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