First non-repeating in a linked list
Last Updated :
24 Jul, 2023
Given a linked list, find its first non-repeating integer element.
Examples:
Input : 10->20->30->10->20->40->30->NULL
Output :First Non-repeating element is 40.
Input :1->1->2->2->3->4->3->4->5->NULL
Output :First Non-repeating element is 5.
Input :1->1->2->2->3->4->3->4->NULL
Output :No NOn-repeating element is found.
- Create a hash table and marked all elements as zero.
- Traverse the linked list and count the frequency of all the elements in the hashtable.
- Traverse the linked list again and see the element whose frequency is 1 in the hashtable.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
int firstNonRepeating(struct Node *head)
{
unordered_map<int, int> mp;
for (Node *temp=head; temp!=NULL; temp=temp->next)
mp[temp->data]++;
for (Node *temp=head; temp!=NULL; temp=temp->next)
if (mp[temp->data] == 1)
return temp->data;
return -1;
}
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 main()
{
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 35);
push(&head, 85);
push(&head, 20);
push(&head, 18);
push(&head, 15);
push(&head, 85);
cout << firstNonRepeating(head);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class GFG
{
static class Node
{
public int data;
public Node next;
public Node(){
this.data = 0;
this.next = null;
}
public Node(int data,Node next){
this.data = data;
this.next = next;
}
};
static int firstNonRepeating(Node head)
{
HashMap<Integer,Integer> mp = new HashMap<>();
for (Node temp=head; temp != null; temp = temp.next){
if(mp.containsKey(temp.data)){
mp.put(temp.data,mp.get(temp.data)+1);
}
else{
mp.put(temp.data,1);
}
}
for (Node temp=head; temp!=null; temp=temp.next){
if (mp.get(temp.data) == 1)
return temp.data;
}
return -1;
}
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
public static void main(String args[])
{
Node head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 35);
head = push(head, 85);
head = push(head, 20);
head = push(head, 18);
head = push(head, 15);
head = push(head, 85);
System.out.print(firstNonRepeating(head));
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
def firstNonRepeating(head):
mp = dict()
temp = head
while (temp != None):
if temp.data not in mp:
mp[temp.data] = 0
mp[temp.data] += 1
temp = temp.next
temp = head
while (temp != None):
if temp.data in mp:
if mp[temp.data] == 1:
return temp.data
temp = temp.next
return -1
def push(head_ref, new_data):
new_node = Node(new_data)
new_node.next = head_ref
head_ref = new_node
return head_ref
if __name__=='__main__':
head = None
head = push(head, 20)
head = push(head, 4)
head = push(head, 35)
head = push(head, 85)
head = push(head, 20)
head = push(head, 18)
head = push(head, 15)
head = push(head, 85)
print(firstNonRepeating(head))
|
C#
using System;
using System.Collections.Generic;
public class Gfg {
static void Main(string[] args)
{
Node head = null;
push(ref head, 20);
push(ref head, 4);
push(ref head, 35);
push(ref head, 85);
push(ref head, 20);
push(ref head, 18);
push(ref head, 15);
push(ref head, 85);
Console.WriteLine(firstNonRepeating(head));
}
static int firstNonRepeating(Node head)
{
Dictionary<int, int> mp
= new Dictionary<int, int>();
for (Node temp = head; temp != null;
temp = temp.next)
if (mp.ContainsKey(temp.data))
mp[temp.data]++;
else
mp[temp.data] = 1;
for (Node temp = head; temp != null;
temp = temp.next)
if (mp[temp.data] == 1)
return temp.data;
return -1;
}
static void push(ref Node headRef, int newData)
{
Node newNode
= new Node{ data = newData, next = headRef };
headRef = newNode;
}
class Node {
public int data;
public Node next;
}
}
|
Javascript
<script>
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
function firstNonRepeating(head)
{
var mp = new Map();
for (var temp=head; temp!=null; temp=temp.next)
{
if(mp.has(temp.data))
{
mp.set(temp.data , mp.get(temp.data)+1)
}
else
{
mp.set(temp.data, 1)
}
}
for (var temp=head; temp!=null; temp=temp.next)
if (mp.get(temp.data) == 1)
return temp.data;
return -1;
}
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
var head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 35);
head = push(head, 85);
head = push(head, 20);
head = push(head, 18);
head = push(head, 15);
head = push(head, 85);
document.write( firstNonRepeating(head));
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N), for the map
Approach : Using two loops
In this approach, we use two loops to traverse the linked list. For each node in the linked list, we traverse the rest of the linked list to check if it is a non-repeating node. If we find a node that is not repeated in the linked list, we return that node.
Traverse the linked list starting from the head node.
For each node in the linked list, traverse the rest of the linked list to check if it is a non-repeating node.
To check if a node is non-repeating, compare its data value with the data value of all the nodes after it in the linked list. If there is another node with the same data value, then the current node is not a non-repeating node.
If a non-repeating node is found, return its data value.
If no non-repeating node is found, return -1 to indicate that no non-repeating node exists in the linked list.
Time Complexity:
C++
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
int firstNonRepeatingNode(Node* head) {
Node* curr = head;
while (curr != NULL) {
bool isNonRepeating = true;
Node* temp = head;
while (temp != NULL) {
if (curr != temp && curr->data == temp->data) {
isNonRepeating = false;
break;
}
temp = temp->next;
}
if (isNonRepeating) {
return curr->data;
}
curr = curr->next;
}
return -1;
}
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 main()
{
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 35);
push(&head, 85);
push(&head, 20);
push(&head, 18);
push(&head, 15);
push(&head, 85);
cout << firstNonRepeatingNode(head);
return 0;
}
|
Java
import java.util.*;
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
static int firstNonRepeatingNode(Node head) {
Node curr = head;
while (curr != null) {
boolean isNonRepeating = true;
Node temp = head;
while (temp != null) {
if (curr != temp && curr.data == temp.data) {
isNonRepeating = false;
break;
}
temp = temp.next;
}
if (isNonRepeating) {
return curr.data;
}
curr = curr.next;
}
return -1;
}
static Node push(Node head_ref, int new_data) {
Node new_node = new Node(new_data);
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
public static void main(String[] args) {
Node head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 35);
head = push(head, 85);
head = push(head, 20);
head = push(head, 18);
head = push(head, 15);
head = push(head, 85);
int result = firstNonRepeatingNode(head);
System.out.println(result);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
def firstNonRepeatingNode(head):
curr = head
while curr != None:
isNonRepeating = True
temp = head
while temp != None:
if curr != temp and curr.data == temp.data:
isNonRepeating = False
break
temp = temp.next
if isNonRepeating:
return curr.data
curr = curr.next
return -1
def push(head_ref, new_data):
new_node = Node(new_data)
new_node.next = head_ref
head_ref = new_node
return head_ref
if __name__ == '__main__':
head = None
head = push(head, 20)
head = push(head, 4)
head = push(head, 35)
head = push(head, 85)
head = push(head, 20)
head = push(head, 18)
head = push(head, 15)
head = push(head, 85)
print(firstNonRepeatingNode(head))
|
Javascript
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function firstNonRepeatingNode(head) {
let curr = head;
while (curr !== null) {
let isNonRepeating = true;
let temp = head;
while (temp !== null) {
if (curr !== temp && curr.data === temp.data) {
isNonRepeating = false;
break;
}
temp = temp.next;
}
if (isNonRepeating) {
return curr.data;
}
curr = curr.next;
}
return -1;
}
function push(head_ref, new_data) {
let new_node = new Node(new_data);
new_node.next = head_ref;
head_ref = new_node;
return head_ref;
}
let head = null;
head = push(head, 20);
head = push(head, 4);
head = push(head, 35);
head = push(head, 85);
head = push(head, 20);
head = push(head, 18);
head = push(head, 15);
head = push(head, 85);
console.log(firstNonRepeatingNode(head));
|
Output:
15
Time Complexity:
The time complexity of this approach is O(n^2), where n is the number of nodes in the linked list. This is because for each node in the linked list, we need to traverse the rest of the linked list to check if it is a non-repeating node. Therefore, the total number of comparisons required is n(n-1)/2, which is O(n^2).
Space Complexity:
The space complexity of this approach is O(1), as we are not using any extra data structures to store the nodes of the linked list or their frequency counts. We are only using a constant amount of memory to store the pointers and variables required to traverse the linked list and check for non-repeating nodes.
Further Optimisations:
The above solution requires two traversals of linked list. In case we have many repeating elements, we can save one traversal by storing positions also in hash table. Please refer last method of Given a string, find its first non-repeating character for details.
Similar Reads
First non-repeating in a linked list
Given a linked list, find its first non-repeating integer element. Examples: Input : 10->20->30->10->20->40->30->NULLOutput :First Non-repeating element is 40.Input :1->1->2->2->3->4->3->4->5->NULLOutput :First Non-repeating element is 5.Input :1->1
12 min read
Linked List meaning in DSA
A linked list is a linear data structure used for storing a sequence of elements, where each element is stored in a node that contains both the element and a pointer to the next node in the sequence. Types of linked lists: Linked lists can be classified in the following categories Singly Linked List
4 min read
Permutation of a Linked List
Given a singly linked list of distinct integers, the task is to generate all possible permutations of the linked list elements. Examples: Input: Linked List: 1 -> 2 -> 3Output: 1 -> 2 -> 31 -> 3 -> 22 -> 1 -> 32 -> 3 -> 13 -> 1 -> 23 -> 2 -> 1Input: Linked L
11 min read
Find first node of loop in a linked list
Given the head of a linked list that may contain a loop. A loop means that the last node of the linked list is connected back to a node in the same list. The task is to find the Starting node of the loop in the linked list if there is no loop in the linked list return -1. Example: Input: Output: 3Ex
14 min read
Rearrange a given linked list in-place
Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list so that the newly formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ... You are required to do this in place without altering the nodes' values. Examples: Input: 1 -> 2 -> 3 -
10 min read
Reverse a Linked List in groups of given size
Given a Singly linked list containing n nodes. The task is to reverse every group of k nodes in the list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should be considered as a group and must be reversed. Example: Input: head: 1 -> 2 -> 3 -> 4 -> 5 ->
3 min read
Singly Linked List in Python
A Singly Linked List is a type of data structure that is made up of nodes that are created using self-referential structures. Each node contains a data element and a reference (link) to the next node in the sequence. This allows for a dynamic and efficient management of data elements. Table of Conte
10 min read
Replace nodes with duplicates in linked list
Given a linked list that contains some random integers from 1 to n with many duplicates. Replace each duplicate element that is present in the linked list with the values n+1, n+2, n+3 and so on(starting from left to right in the given linked list). Examples: Input : 1 3 1 4 4 2 1 Output : 1 3 5 4 6
9 min read
Circular Linked List in Python
A Circular Linked List is a variation of the standard linked list. In a standard linked list, the last element points to null, indicating the end of the list. However, in a circular linked list, the last element points back to the first element, forming a loop. In this article, we will discuss the c
13 min read
Intersection of two Sorted Linked Lists
Given the head of two sorted linked lists, the task is to create a new linked list that represents the intersection of the two original lists. The new linked list should be created without modifying the original lists. Note: The elements in the linked lists are not necessarily distinct. Example: Inp
15+ min read
Swap nodes in a linked list without swapping data
Given a singly linked list with two values x and y, the task is to swap two nodes having values x and y without swapping data. Examples: Input: 1->2->3->4->5, x = 2, y = 4Output: 1->4->3->2->5 Input: 10->15->12->13->20->14, x = 10, y = 20Output: 20->15->1
15+ min read
Write a function to get Nth node in a Linked List
Given a LinkedList and an index (1-based). The task is to find the data value stored in the node at that kth position. If no such node exists whose index is k then return -1. Example: Input: 1->10->30->14, index = 2Output: 10Explanation: The node value at index 2 is 10 Input: 1->32->
11 min read
Insertion in Unrolled Linked List
An unrolled linked list is a linked list of small arrays, all of the same size where each is so small that the insertion or deletion is fast and quick, but large enough to fill the cache line. An iterator pointing into the list consists of both a pointer to a node and an index into that node contain
11 min read
Basic Terminologies of Linked List
Linked List is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers. Linked List forms a series of connected nodes, where each node stores the data and the address of the next node. Node Structure: A node in a linked list typically
3 min read
Print nodes of linked list at given indexes
Given head of two singly linked lists, first one is sorted and the other one is unsorted. The task is to print the elements of the second linked list according to the position pointed out by the data in the first linked list. For example, if the first linked list is 1->2->5, then you have to p
15+ min read
Second Smallest Element in a Linked List
Given a Linked list of integer data. The task is to write a program that efficiently finds the second smallest element present in the Linked List. Examples: Input : List = 12 -> 35 -> 1 -> 10 -> 34 -> 1Output : The second smallest element is 10.Input : List = 10 -> 5 -> 10Output
15+ min read
Two-Pointer Technique in a Linked List
The two-pointer technique is a common technique used in linked list problems to solve a variety of problems efficiently. It involves using two pointers that traverse the linked list at different speeds or in different directions. Use Cases of Two-Pointer Technique in a Linked List:1. Finding the Mid
3 min read
Reverse a doubly linked list in groups of K size
Given a Doubly linked list containing n nodes. The task is to reverse every group of k nodes in the list. If the number of nodes is not a multiple of k then left-out nodes, in the end should be considered as a group and must be reversed. Examples: Input: 1 <-> 2 <-> 3 <-> 4 <-
15+ min read
Move first element to end of a given Linked List
Write a C function that moves first element to end in a given Singly Linked List. For example, if the given Linked List is 1->2->3->4->5, then the function should change the list to 2->3->4->5->1. Algorithm: Traverse the list till last node. Use two pointers: one to store the
14 min read