ในปัญหานี้ เราได้รับ linked list LL ขนาด N ภารกิจของเราคือ สร้างโปรแกรมหาองค์ประกอบที่ไม่ซ้ำใน linked list
Linked list คือลำดับของโครงสร้างข้อมูล ซึ่งเชื่อมต่อกันผ่านลิงก์
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: LL = 4 => 6 => 2 => 4 => 1 => 2 => 6 => 5 Output: 1
คำอธิบาย -
องค์ประกอบที่มีความถี่เกิดขึ้นครั้งเดียวคือ 1 และ 6 จากเหล่านี้ 1 เกิดขึ้นก่อนใน linked list
วิธีการแก้ปัญหา
วิธีหนึ่งในการแก้ปัญหาคือการสร้างตารางแฮชที่จะเก็บองค์ประกอบและความถี่ของการเกิดขึ้น เพื่อหาค่าที่ไม่ซ้ำแรกใน linked list เราจะเดินทางผ่าน linked list และแทรกองค์ประกอบที่ไม่อยู่ใน hash map ลงไปด้วยความถี่เริ่มต้น 1 หากองค์ประกอบใดอยู่ใน hash map ให้เพิ่มความถี่ หลังจากเดินทางผ่าน linked list เราจะตรวจสอบค่าใน hash map ที่ความถี่เป็นหนึ่งและคืนค่าตัวแรกที่พบ
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#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
