First Non-Repeating Element in a Linked List in C++

In this problem, we are given a linked list LL of size N. Our task is to create a program for finding non-repeating in linked list.

Linked list is a sequence of data structures, which are connected together via links.

Let's take an example to understand the problem,

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

Explanation −

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

Solution Approach

An approach to solve the problem is by creating a hash table that will store elements and their occurrence frequency. To find the first non-repeating value in the linked list, we will traverse the linked list and insert elements that are not present in the hash map to it with initial occurrence frequency 1. If any element is present in the hash map increase its occurrence frequency. After traversing the linked list, we will check for the value in the hash map whose occurrence frequency is one and return the first values the is encountered.

Example

Program to illustrate the working of our solution

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

Output

The first non repeating element of the linked list is 1